题目描述（中等难度）

给定二叉树的两个节点，找出两个节点的最近的共同祖先。

解法一

刚做的 是这个题的子问题， 235 题是让我们在二叉搜索树中找两个节点的最近的共同祖先。当时分了三种情况。

• 如果给定的两个节点的值都小于根节点的值，那么最近的共同祖先一定在左子树
• 如果一个大于等于、一个小于等于根节点的值，那么当前根节点就是最近的共同祖先了

通过确定两个节点的位置，然后再用递归去解决问题。

之前是二叉搜索树，所以通过和根节点的值进行比较就能知道节点的是在左子树和右子树了，这道题的话我们只有通过遍历去寻找给定的节点，从而确定节点是在左子树还是右子树了。

遍历采用 的中序遍历，栈的形式。

解法二

参考 。

我们注意到如果两个节点在左子树中的最近共同祖先是 ，那么当前树的最近公共祖先也就是 r，所以我们可以用递归的方式去解决。

对于 lowestCommonAncestor 这个函数的理解的话，它不一定可以返回最近的共同祖先，如果子树中只能找到 p 节点或者 q 节点，它最终返回其实就是 p 节点或者 q 节点。这其实对应于最后一种情况，也就是 leftCommonAncestor 和 rightCommonAncestor 都不为 null，说明 p 节点和 q 节点分处于两个子树中，直接 return root。

相对于解法一的话快了很多，因为不需要每次都遍历一遍二叉树，这个解法所有节点只会遍历一次。

解法三

root 节点一定是 节点和 q 节点的共同祖先，只不过这道题要找的是最近的共同祖先。

从 root 节点出发有一条唯一的路径到达 p。

从 root 节点出发也有一条唯一的路径到达 q。

可以抽象成下图的样子。

事实上，我们要找的最近的共同祖先就是第一次出现分叉的时候，也就是上图中的 r。

那么怎么找到 r 呢？

我们可以把从 root 到 p 和 root 到 q 的路径找到，比如说是

root -> * -> * -> r -> x -> x -> p

root -> * -> * -> r -> y -> y -> y -> y -> q

比如倒着遍历 到 q 的路径。

依次判断 q 在不在 root 到 p 的路径中，y 在不在？ … r 在不在？ 发现 r 在，说明 r 就是我们要找到的节点。

代码实现的话，因为我们要倒着遍历某一条路径，所以可以用 HashMap 来保存每个节点的父节点，从而可以方便的倒着遍历。

另外我们要判断路径中有没有某个节点，所以我们要把这条路径的所有节点存到 HashSet 中方便判断。

寻找路径的话，我们一开始肯定不知道该向左还是向右，所以我们采取遍历整个树，直到找到了 p 和 q ，然后从 p 和 开始，通过 hashMap 存储的每个节点的父节点，就可以倒着遍历回去确定路径。

总

解法一的话是受到上一题的影响，理论上应该可以直接想到解法二的，是一个很常规的递归的问题。解法三的话，想法很新颖。

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^