LCA 类问题是二叉树的高频问题之一；

• 有只给 root 的；

• 还有不给 root 给 parent pointer 的。

• 想面 FB，最好把各种二叉树问题的 recursion / iteration 还有 root / parent pointer 的写法都练熟才行，只 AC 是不够的。

Lowest Common Ancestor of a Binary Search Tree

递归

迭代

复杂度分析

时间复杂度 O(n)，如果 Tree 的形状是一条线往左或右的 full binary tree 的话。

Lowest Common Ancestor of a Binary Tree

递归 ✓

迭代 ✓

parent指针 todo

复杂度分析 ✓

递归: 另一种时间复杂度的分析方式是，这题的递归结构不过是个 post-order traversal，遍历的复杂度当然是 O(n).

想到这，迭代的写法也比较明显了，写个 post-order traversal 就行。

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

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

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

递归利用额外的数据结构

   class Entity{
     public int count;
     public TreeNode root;

     Entity(int count, TreeNode root){
         this.count = count;
         this.root = root;
     }
 }
  public Entity lca(TreeNode root,TreeNode p,TreeNode q){
        if(root==null) return new Entity(0, null);
        Entity left = lca(root.left, p, q);
        if(left.count == 2)
            return left;
        Entity right = lca(root.right, p, q);
        if(right.count == 2)
            return right;
        int numTotal = left.count + right.count;
        if(root == p || root ==q){
            numTotal++;
        }
        return new Entity(numTotal, root);
    }

迭代: 用map存储每个节点的parent, 计算两个节点的高度后向上搜索

给一个 二叉树 ， 求最深节点的最小公共父节点。

http://www.1point3acres.com/bbs/thread-199739-1-1.html

       1
      / \
     2   3
        / \
       4   5

    return 3

       1
      / \
     2   3
    /   / \
   6   4   5

   return 1

这题的关键点只有一个：意识到只需要求最底层 level 最左面和最右面节点的 LCA 就可以了。

因此这个问题的递归与迭代就变成了两个子问题：

• 如何递归求 level order 和 LCA, 利用entity数据结构递归.

• 如何迭代求 level order 和 LCA, map存储父节点,bfs找到最底层最左右两点, 向上搜索.