88/474/578. Lowest Common Ancest

Description

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.

88:Assume two nodes are exist in tree.

474:The node has an extra attribute parent which point to the father of itself. The root's parent is null.

578:node A or node B may not exist in tree.

Example

Example 1:

Input：{1},1,1

Output：1

Explanation：

For the following binary tree（only one node）:

        1

LCA(1,1) = 1

Example 2:

Input：{4,3,7,#,#,5,6},3,5

Output：4

Explanation：

For the following binary tree:

      4

    / \

    3  7

      / \

      5  6

LCA(3, 5) = 4

思路：

同样的题有三个变种，88是两个node一定在树上， 474是多了个parent的属性指向了每个node的父节点，578是点不一定在树上，解法也各不相同。

474：其中最简单的就是474，只需要找到相应的A点遍历其父节点及父节点的父节点存成字典，然后在字典中查找B及其父节点存在的位置。还有一种做法就是两层循环遍历A和B的父节点并比较，前者效率会高一点，这个题被定为easy是因为不需要深度优先搜索之类的。

88：因为确定Node一定在树上，那么进行深度优先搜索时就一定会找到node，用分治的思想，分别从左子树和右子树找node，在左右两边找到一个Node就可以返回，不需要再深入，因为左边找到，右边没有找到的话，说明另一个节点是左边节点的子节点，同理右边也是，如果两边都找到了，那就是它俩第一次共同的根节点就是LCA。

578：这个题不同的是增加了Node可能不在树上的约束，按照88的方法求出来的LCA可能就并不是真正的LCA，因为还有一种可能就是有一个Node并不在树上，所以这道题需要全部搜索一遍节点去判断A， B在不在树上，只有AB都在树上得到的结果才是有效结果,因为要遍历整棵树，递归函数会写在return条件前面不像88只要找到节点就返回并不进行接下来的左右节点遍历。

代码：

88

474

578