[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可以被传上去

代码如下：

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