二叉树15：二叉树的最近公共祖先

LeetCode 236 &＃xff0c;给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 例如&＃xff0c;给定如下二叉树:

输入:
root &＃61; [3,5,1,6,2,0,8,null,null,7,4]
p &＃61; 5, q &＃61; 1
输出&＃xff1a;3
解释&＃xff1a;节点 5 和节点 1 的最近公共祖先是节点 3。

要想找到两个节点的最近公共祖先节点&＃xff0c;我们可以从两个节点往上找&＃xff0c;每个节点都往上 走&＃xff0c;一直走到根节点&＃xff0c;那么根节点到这两个节点的连线肯定有相交的地方&＃xff0c;如果是从上 往下走&＃xff0c;那么最后一次相交的节点就是他们的最近公共祖先节点。我们就以找6和7的最 近公共节点来画个图看一下

我们看到6和7公共祖先有5和3&＃xff0c;但最近的是5。我们只要往上找&＃xff0c;找到他们第一个相同 的公共祖先节点即可&＃xff0c;但怎么找到每个节点的父节点呢&＃xff0c;我们只需要把每个节点都遍历 一遍&＃xff0c;然后顺便记录他们的父节点存储在Map中。我们先找到其中的一条路径&＃xff0c;比如 6→5→3&＃xff0c;然后在另一个节点往上找&＃xff0c;由于7不在那条路径上&＃xff0c;我们找7的父节点是2&＃xff0c;2 也不在那条路径上&＃xff0c;我们接着往上找&＃xff0c;2的父节点是5&＃xff0c;5在那条路径上&＃xff0c;所以5就是他们 的最近公共子节点。

其实这里我们可以优化一下&＃xff0c;我们没必要遍历所有的结点&＃xff0c;我们一层一层的遍历(也就 是BFS)&＃xff0c;只需要这两个节点都遍历到就可以了&＃xff0c;比如上面2和8的公共结点&＃xff0c;我们只需 要遍历到第3层&＃xff0c;把2和8都遍历到就行了&＃xff0c;没必要再遍历第4层了。

看递归的代码&＃xff1a;

public TreeNode lowestCommonAncestor(TreeNode cur, TreeNode p, TreeNode q) {if (cur &＃61;&＃61; null || cur &＃61;&＃61; p || cur &＃61;&＃61; q)return cur;TreeNode left &＃61; lowestCommonAncestor(cur.left, p, q);TreeNode right &＃61; lowestCommonAncestor(cur.right, p, q);//如果left为空&＃xff0c;说明这两个节点在cur结点的右子树上&＃xff0c;我们只需要返回右子树查找的结果即可 if (left &＃61;&＃61; null)return right; //同上if (right &＃61;&＃61; null)return left;
//如果left和right都不为空&＃xff0c;说明这两个节点一个在cur的左子树上一个在cur的右子树上&＃xff0c;
// 我们只需要返回cur结点即可。return cur;}

对于这类稍微复杂一些的题目&＃xff0c;代码不见得很复杂&＃xff0c;我们会递归写法就足够了&＃xff0c;关键是自己必须能想清楚为什么这么做可以。