LCA

LCA of BST

• LCA 问题就是判断给定两个 node {p,q} 与 root 之间的相对位置。在 BST 里这种相对关系看 node.val 就可以。
• 时间复杂度 O(n)
• Worst case 如果 Tree 的形状是一条线往左或右的 full binary tree 的话。
• 因为是尾递归(递归后没有别的操作，例如说不需要回溯)，显而易见的改法是用 while循环省去递归占用的系统栈空间；

  public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Got to check if p and q is null as well;
        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;
    }
  }
  

LCA of BT

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes. The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Analysis

• Binary Tree -> Divide & Conquer 所以考虑的时候，应该从如何将问题分解成子问题入手，而非直接去找解决问题的方法（通项）
• Divide 分解子问题，一般都有返回值
  • 分析的时候可以画图，发现从root开始往下搜索，先搜索左子树，如果左边遇到任何==p或者q的值，则可以把这个值返回到当前的root，然后对另一侧（即右子树）进行搜索，如果右字数也遇到p或者q的值，则返回到root，这时候对于root的搜索，左右子树均有返回值，说明root就是他们的LCA
    • 如果右边的返回值为null，说明在root节点的搜索只能找到一个点，需要往上一层搜索另外一侧
      • 不管如何都需要搜索整个树的所有节点
      • 这道题的tricky之处在于，理解返回值与LCA的定义

        • if both p and q exist in Tree rooted at root, then return their LCA
        • if neither p and q exist in Tree rooted at root, then return null
        • if only one of p or q (NOT both of them), exists in Tree rooted at root, return it

• corner case
  • 当A或B不在tree里
  • A或B为root
• 这种解法的时间复杂度是 O(n)，因为对于一个 node 来讲，它只被调用一次
• 极少会有 O(n^2) 的 binary tree 算法，因为那意味着每个节点相对于整个树重新计算，而不再是自己从属的路径或者高度。

Solution

public class Solution {
    // 在root为根的二叉树中找A,B的LCA:
    // 如果A和B都在root里，返回root
    // 如果只有A在root里，就返回A
    // 如果只有B在root里，就返回B
    // 如果都没有，就返回null
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
    if (root == null || root == node1 || root == node2) {
        return root;
    }

    // Divide
    TreeNode left = lowestCommonAncestor(root.left, node1, node2);
    TreeNode right = lowestCommonAncestor(root.right, node1, node2);

    // Conquer
    if (left != null && right != null) {
        return root;
    } 
    if (left != null) {
        return left;
    }
    if (right != null) {
        return right;
    }
    return null;
}
}

Time Complexity: O(n)

Follow ups

if node has parent point

Analysis

分别获取A和B到root的paths，再根据path倒序比较，遇到第一个不同的则跳出，前一个就是LCA

 public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root, ParentTreeNode A, ParentTreeNode B) {
        ArrayList<ParentTreeNode> pathA = getPath2Root(A);
        ArrayList<ParentTreeNode> pathB = getPath2Root(B);

        int indexA = pathA.size() - 1;
        int indexB = pathB.size() - 1;

        ParentTreeNode lowestAncestor = null;
        while (indexA >= 0 && indexB >= 0) {
            if (pathA.get(indexA) == pathB.get(indexB)) {
                break;
            }
            lowestAncestor = pathA.get(indexA);
            indexA--;
            indexB--;
        }

        return lowestAncestor;
    }

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

if A or B may not be in the tree

Analysis

• 引入ResultType，存放A或者B的是否在树上进行判断

class ResultType {
    public boolean a_exist, b_exist;
    public TreeNode node;
    ResultType(boolean a, boolean b, TreeNode n) {
        a_exist = a;
        b_exist = b;
        node = n;
    }
}

public class Solution {
    /**
     * @param root The root of the binary tree.
     * @param A and B two nodes
     * @return: Return the LCA of the two nodes.
     */
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {
        // write your code here
        ResultType rt = helper(root, A, B);
        if (rt.a_exist && rt.b_exist)
            return rt.node;
        else
            return null;
    }

    public ResultType helper(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null)
            return new ResultType(false, false, null);

        ResultType left_rt = helper(root.left, A, B);
        ResultType right_rt = helper(root.right, A, B);

        boolean a_exist = left_rt.a_exist || right_rt.a_exist || root == A;
        boolean b_exist = left_rt.b_exist || right_rt.b_exist || root == B;

        if (root == A || root == B)
            return new ResultType(a_exist, b_exist, root);

        if (left_rt.node != null && right_rt.node != null)
            return new ResultType(a_exist, b_exist, root);
        if (left_rt.node != null)
            return new ResultType(a_exist, b_exist, left_rt.node);
        if (right_rt.node != null)
            return new ResultType(a_exist, b_exist, right_rt.node);

        return new ResultType(a_exist, b_exist, null);
    }
}