[LintCode]Lowest Common Ancestor

前提条件是查询的两个节点node1和node2是在tree里的，如果没有这个前提条件，我们可以先遍历一遍tree来看这两个node是不是在tree里，由于LCA的算法是O(n)，执行之前确定两个node是否在tree里也是O(n)的，不会影响时间复杂度。这里我们假设这个前提条件是成立的。同样用bottom-up的方法，return的策略如下：

• 如果curr是null，return null
• 如果curr等于node1或者node2，return curr。这时候有两种情况，curr就是LCA或者LCA是其他。，如果curr就是LCA那么它会被一直return上去，如果不是的话，找到其他的会return真正的LCA
• 如果left和right return的都不是null，说明curr就是LCA，return curr, curr会一直被return上去
• 如果left和right return的都是null，return null
• 如果left或者right不等于null，return 不是null的那一个，这是为了保证可能是结果的node可以被传上去

代码如下：

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/
	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) {
	if (root == null)
	return null;
	if (root == A || root == B)
	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;
	}
	}

view raw LCA.java hosted with ❤ by GitHub

可能的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