1/16，LCA

LCA是binary tree的高频问题之一。碰到此类题，如果面试官没说具体细节，要问清楚，没说的假设一定要make sure。

• 树是不是BST
• 节点可能不在树上
• 节点有没有parent pointer

Lowest Common Ancestor of a Binary Search Tree

LCA问题就是用两个node找root，在BST里，判断往左或往右走直接和root.val比较就可以了。也就是说，当比较的情况是node1.val <= root.val <= node2.val，就找到root了。因为allow a node to be a descendant of itself，所以在等于的情况下，一个node可作为common ancestor。

• 迭代 ✔️
• 递归 ✔️
• 复杂度分析 ✔️

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // sanity check 
        if (root == null || p == null || q == null) return null;

        while (root != null) {
            if (root.val > p.val && root.val > q.val) root = root.left;
            else if (root.val < p.val && root.val < q.val) root = root.right;
            else return root;
        }
        return root;
    }
}

改成递归很容易，但会占用系统的stack memory

递归改迭代，因为是尾递归，显而易见的改法是用while循环省去递归占用的系统栈空间。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;    // considering p or q does not exist in tree

        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

1/1复习，复杂度O(lgn)，树的高度。

2/17补充，觉得这题还需要clarify的地方是，可能p，q不在树里，如果有一个不在，就应该返回None，需要先检查存在性。

Lowest Common Ancestor

如果不是BST的话，做法就完全不一样了。考虑递归的想法，首先派两个小人从根节点处出发，分别尝试去他们的左右子树里找到节点。当两个node在左右子树都被找到后，返回相应的root。

• 递归 ✔️
• 复杂度分析 ✔️

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // base case
        if (root == null || p == root || q == root) return root;

        // divide 
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // conquer
        if (left != null && right != null) return root;
        else return (left == null) ? right : left;
    }
}

要注意的细节是，base case:到达最底层时还没找到，就返回null，如果找到的节点是A or B，就返回当前节点。还需要注意，在分治步骤后的conquer的判断语句。就是看左右子树是否都找到了节点，如果是的话，就返回当前的root。如果只在一边找到了，就返回找到的那一边。

所有节点会检查到的次数不超过一次，时间复杂度是O(n)。

还有个做法是先inorder pre-process一遍，把binary tree当BST用。因为in-order的index就像BST里的大小一样，可以直接确定几个节点在树中的相对位置。然后我们从root开始一层一层往下搜索，保证每次循环的root都一定valid。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        HashMap<TreeNode, Integer> map = new HashMap<>();
        Deque<TreeNode> stack = new LinkedList<>();

        TreeNode cur = root;
        int index = 0;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode node = stack.pop();
            map.put(node, index++);
            cur = node.right;
        }

        return getLCA(root, p, q, map);
    }

    private TreeNode getLCA(TreeNode root, TreeNode p, TreeNode q, HashMap<TreeNode, Integer> map) {
        if (root == null || root == p || root == q) return root;

        while (root != null) {
            if (map.get(p) < map.get(root) && map.get(q) < map.get(root)) {
                root = root.left;
            } else if (map.get(p) > map.get(root) && map.get(q) > map.get(root)) {
                root = root.right;
            } else {
                break;
            }
        }
        return root;
    }
}

Lowest Common Ancestor III

一种情况是，如果A和B至少有一个不在树上，这样的话就不能直接用上面的解法了，否则返回的可能是在一边找到的那个点，实际上如果有一个不存在，就不该有common ancestor。可以先分别验证A和B的存在性，通过遍历找点，如果两个都被找到的话，再用上面的方法找LCA。(first clarify validness and existence - what if the root, or at least one node is empty? do we need to consider the situation where node doesn't exist in the tree?)

• 递归 ✔️

public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        if (root == null || A == null || B == null) return null;

        // use recursive or iterative way to check
        if (!preorderSearch(root, A)) return null;  
        if (!preorderSearch(root, B)) return null;

        return getLCA(root, A, B);
    }

    private boolean preorderSearch(TreeNode root, TreeNode node) {
        if (root == null) return false;
        if (root == node) return true;

        preorderSearch(root.left, x) || preorderSearch(root.right, x)
    }

    private TreeNode getLCA(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null || A == null || B == null) return null;
        if (root == A || root == B) return root;

        TreeNode left = getLCA(root.left, A, B);
        TreeNode right = getLCA(root.right, A, B);

        if (left != null && right != null) return root;
        else return (left == null) ? right : left;
    }

11月29号再写这道感觉好简单啊，注意逻辑结构就行了。

1/1补充，如果这题没说A,B在不在树上，那一定要先check。

3/10，注意出口返回和调用递归函数之间的逻辑。

Lowest Common Ancestor II

如果是node具有parent pointer的情况，使用hashset就行了。想法是自节点A向root遍历，同时把每个被访问的节点add到set里面。再从节点B向上遍历，过程中如果被访问的节点在hashtable里，就返回这个节点。

• 迭代 ✔️
• 复杂度分析 ✔️

w/ hashset solution:
public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root, ParentTreeNode A, ParentTreeNode B) {
        // write your code here
        if (root == null || A == null || B == null) return null;

        HashSet<ParentTreeNode> set = new HashSet<ParentTreeNode>();
        if (root == null || q == null || p == null) return null;

        Set<TreeNodeParent> set = new HashSet<>();
        while(p != null) {
            set.add(p);
            p = p.parent;
        }

        while(q != null) {
            if (set.contains(q)) {
                break;
            }
            q = q.parent;
        }
        return q;
        return root;
    }

w/o hashset: use 2 ArrayLists to store all the treenodes in the path from A or B to the root. 
and then perform a backward search on the two path, stop when we find the first different treenode. 

    public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root, ParentTreeNode A, ParentTreeNode B) {
        // write your code here
        if (root == null || A == null || B == null) return null;

        ArrayList<ParentTreeNode> pathA = getPath2Root(A);
        ArrayList<ParentTreeNode> pathB = getPath2Root(B);

        int sizeA = pathA.size() - 1;
        int sizeB = pathB.size() - 1;

        ParentTreeNode lowestAncestor = null;
        while (sizeA >= 0 && sizeB >= 0) {
            if (pathA.get(sizeA) != pathB.get(sizeB)) {
                break;
            }
            lowestAncestor = pathA.get(sizeA);
            sizeA--;
            sizeB--;
        }
        return lowestAncestor;
    }

    private ArrayList<ParentTreeNode> getPath2Root(ParentTreeNode root) {
        ArrayList<ParentTreeNode> res = new ArrayList<>();
        while (root != null) {
            res.add(root);
            root = root.parent;
        }
        return res;
    }

想象成找两条线交点的过程。如果树是full binary tree有n个节点，那最坏情况是A和B分别是左右子树的叶节点，root是LCA，相当于走了两遍树的高度，时间复杂度是O(lgn)。注意assume存在LCA。