236. Lowest Common Ancestor of a Binary Tree

题目：

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              
    ___5__          ___1__
   /              /      
   6      _2       0       8
         /  
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

链接： http://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

5/9/2017

看别人答案

首先这道题保证了两个节点都在树里，所以我们返回值才有意义。

思路

1. null返回null

2. root为其中之一时返回root

3. p, q在2边时返回root

4. p, q在单边时返回单边

5. p, q都不在的时候返回null，（随便返回一边）

当问题到达最上层Root的时候是什么情况？2，3都没问题。第4种情况的话这个单边返回来的值就是LCA，而第5种情况在最上层不会出现--因为题目说了都在tree里的。

另外注意第9行，返回的并不一定是root.left而是left，可能是更低的一个node

 1 public class Solution {
 2     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 3         if (root == null) return null;
 4         if (root == p || root == q) return root;
 5         
 6         TreeNode left = lowestCommonAncestor(root.left, p, q);
 7         TreeNode right = lowestCommonAncestor(root.right, p, q);
 8         if (left != null && right != null) return root;
 9         return left != null? left: right;
10     }    
11 }

参考

里面提到了tarjan's algorithm

https://www.hrwhisper.me/algorithm-lowest-common-ancestor-of-a-binary-tree/

别人的答案

recursive

https://discuss.leetcode.com/topic/18561/4-lines-c-java-python-ruby

iterative

https://discuss.leetcode.com/topic/18652/iterative-solutions-in-python-c

Java iterative但是没有看明白，貌似是，把找p,q过程中的parent加到map中，然后当都找到之后建立一个set，先加p的parent，再找q的parent，第一个在set当中的就是共同祖先。O(n)复杂度

https://discuss.leetcode.com/topic/27479/java-python-iterative-solution

附，LintCode有道类似的题，但是不保证p,q在树里，这就导致在最高层root时，无法判断来自同一边的LCA是真正在子树就找到的LCA还是仅仅只找到了一个node的临时LCA。需要有附加信息来判断。