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.
Have you met this question in a real interview?
Yes
Example
For the following binary tree:
4 / \ 3 7 / \ 5 6 LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
public class Solution { /** * @param root: The root of the binary search tree. * @param A and B: two nodes in a Binary. * @return: Return the least common ancestor(LCA) of the two nodes. */ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) { // write your code here if(root == null) return root; if(A == root|| B == root) return root; TreeNode left = lowestCommonAncestor(root.left,A,B); TreeNode right = lowestCommonAncestor(root.right,A,B); if(left != null && right != null){ return root; } else{ return left == null ? right : left; } } }可能的Follow up是，对于k-way tree，如何寻找LCA，我们在这里说一下思路，就不写代码了，return的策略如下：如果curr是null，return null如果curr是等于node1....nodek，return curr。这时候有两种情况，curr就是LCA或者LCA是其他。如果curr就是LCA那么它会被一直return上去，如果不是的话，找到其他的会return真正的LCA如果left和right return的都是null，return null如果k个子树return的不是null，说明curr是LCA，return curr如果n个子树(2 <= n < k)个子树return的不是null，说明curr有可能是LCA，return curr如果只有1个子树return的不是null，继续把那个node return上去LCA的情况还是一样，要不是在k各node里，要不是其他的node，根据以上的策略，我们可以找到正确的LCA。Follow up：Calculate Distance of Two Nodes in Binary Tree