JoyceeLee

/*
 * 4.9 You are given a binary tree in which each node contains a value. Design an algorithm
 * to print all paths which sum to a given value. 
 * Note : The path does not need to start or end at the root or a leaf.
 */


/* 
 * DFS, check if the current node is the end of the valid path
 *

JoyceeLee

/*
 * 4.8 You have two very large binary trees: T1, with millions of nodes, and T2, with
 * hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
 * A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n
 * is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.
 */


/*
 * The 1st solution is build the in-order and pre-order traversal of both t1 and t2,

JoyceeLee

/*4.7 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. 
* Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.*/

public class Solution {
    public TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(!cover(root, p) || !cover(root, q)) {
            return null;
        }
        return findCommon(root, p, q);
    }

JoyceeLee

/*4.6 Write an algorithm to find the 'next' node (i.e., in-order successor) of a given node in a binary search tree. 
* You may assume that each node has a link to its parent.
*/

public class Solution {
    public TreeNode findNext(TreeNode node) {
        if(node==null) return null;
        if(node.right!=null) {
            node = node.right;
            while(node.left!=null) {

JoyceeLee

/*4.5 Implement a function to check if a binary tree is a binary search tree.*/

public class Solution {
    public boolean isBST(TreeNode root) {
        return checkBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    checkBST(TreeNode root, int min, int max) {
        if(root==null) return true;
        return root.val>min && root.val<max && checkBST(root.left, min, root.val) && checkBST(root.right, root.val, max);
    }

JoyceeLee

/*4.4 Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth 
* (e.g., if you have a tree with depth D,you'll have D linked lists).
*/

public class Solution {
    public LinkedList<LinkedList<Node>> createLinkedList(TreeNode root) {
        LinkedList<LinkedList<Node>> ret = LinkedList<LinkedList<Node>>();
        if(root==null) return ret;
        LinkedList<Node> level = new LinkedList<Node>();
        level.add(root);

JoyceeLee

/*4.3 Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree 
with minimal height.*/

public class Solution {
    public TreeNode arrayToBST(int[] A) {
        return buildTree(A, 0, A.length);
    }
    public TreeNode buildTree(int[] A, int s, int e) {
        if(s>=e) return null;
        int mid = (s+e) >> 1;

JoyceeLee

/*4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.*/
/* BFS or DFS */
Compare DFS & BFS:
 - DFS is more simple 'cause it can be implement by recursion
 - BFS may find the shortest way, well DFS one node very deep ever before visit the immediate node

public enum State {
    Visited, Unvisited, Visiting;
}
class Node {

JoyceeLee

/*4.1 Implement a function to check if a binary tree is balanced. For the purposes of this question, 
* a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.
*/


// Solution 1
public class Solution {
    public boolean balancedBinaryTree(TreeNode root) {
        if(root==null) return true;
        if(Math.abs(getHeight(root.left)-getHeight(root.right))>1) return false;

JoyceeLee

/*3.7 An animal shelter holds only dogs and cats, and operates on a strictly "first in, first out" basis. 
* People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, 
* or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). 
* They cannot select which specific animal they would like. 
* Create the data structures to maintain this system and implement operations 
* such as enqueue, dequeueAny, dequeueDog and dequeueCat.
* You may use the built-in LinkedList data structure.
*/

abstract class Animal {