大家好，今天我们要讨论的主题是，二叉树中两节点的最近公共祖先。

题目选自LeetCode 236，具体如下。已知二叉树的根节点指针root，树上的两个不同节点的指针p和q，求p、q两个节点的最近公共祖先。

例如，如果root、p和q分别指向3、6、4，那么就应该返回节点5的地址。

我们可以再多举几个例子。例如，p和q指向1和2，则应该返回3的地址，如果指向5和4，则返回5本身的地址。

问题分析

为了求出树上任意两个节点的最近公共祖先，需要先明确如下3个问题。

1，如何求某节点的祖先节点?

2，如何求两节点的公共祖先?

3，如何求所有公共祖先中最近的那个节点?

关于问题1，求某节点的祖先节点，就是求根节点到该节点，路径上的所有节点。例如，求q的祖先节点，就需要找到3、5、2、4这些节点的地址。

关于问题2，求两个节点的公共祖先，就是求，同时出现在，两个节点路径上的节点。例如，根节点到p的路径上有3、5、6，到q的路径上有3、5、2、4，两条路径上同时出现了3与5，所以它们是p与q的公共祖先。

关于问题3，求最近的公共祖先，就是求，同时出现在两条路径上，离根最远、离两节点最近的节点。例如，p和q的公共祖先是3和5，5距离根节点最远，距离p、q最近，所以5就是p和q的最近公共祖先。

算法设计

因此总结题目的算法设计如下，其中包括2个步骤。

1.求出p和q两节点的路径。

2.求出两条路径上最后一个地址相同的节点，即为最近的公共祖先。

对于步骤1，求某节点的路径，就是要保存根节点到该节点之间，所有节点的指针。在这个过程中，需要设置一个栈，来存储路径上的节点指针。

这里需要特别说明，栈中保存的是节点的地址，而不是节点中的数据。我们为了方便说明算法，才使用数据来表示某个节点。实际上，栈中应该保存，是这样的16进制地址。

当找到该节点时，从栈底到栈顶存储的节点即为从根节点到该节点的路径。例如，q的路径是3、5、2、4。在找到q时，从栈底到栈顶就会存储3、5、2、4这四个节点的指针。

在搜索路径时，需要使用二叉树的深度优先搜索算法。从根节点开始遍历，直到找到待搜索的节点。例如，搜索q节点，从根节点3开始，依次遍历3、5、6、2、7、4，最终找到节点q。

具体来说，在前序遍历到某一节点时，节点的地址入栈。例如，当遍历到节点6时，节点3、5、6按照顺序存储至栈中。

当某节点完成遍历后，需要将该节点的地址从栈中弹出。例如，当节点6完成遍历后，需要将6从栈中弹出。

接着搜索会回溯到节点5，而栈中刚好存储了从根节点到节点5路径上的节点。因此，上述算法就保证了，栈会一直存储，根节点到当前正在遍历节点的路径。

搜索q节点的详细过程

搜索q节点路径的具体过程如下。

首先访问根节点3，3入栈。然后是5和6，入栈。6是叶节点，访问结束后，将6从栈中弹出。

这样，5的左子树就完成了搜索，然后要继续搜索5的右子树。

接着节点2入栈，然后是7。7是叶节点，入栈后即出栈。节点2的左子树完成搜索后，访问2的右子树，节点4。

这时就找到了目标节点q，搜索结束。此时从栈低到栈顶存储的3、5、2、4，即为根节点至q节点的路径。

求最近的公共祖先

得到p和q的路径后，在两条路径上寻找离根节点最远的公共节点。这个过程需要使用指针，同时遍历p和q的路径，最后一个相同的节点即为最近公共祖先。

例如， p的路径是3、5、6，q的路径是3、5、2、4 ，同时出现两条路径上的节点是3和5。最后一个相同节点是5，所以5是最近的公共祖先。

代码实现

定义函数dfs，求指定节点的路径。函数有4个参数， node指向当前正在搜索的节点，search指向待查找的节点，stack是存储节点路径的栈， path存储search节点的路径。

在函数中，如果当前访问的node指向空，搜索结束，直接返回。否则将node压入栈中。

如果node和search相等，则说明找到了目标节点，stack中就存储了结果路径，将path赋值为stack，函数返回。否则继续递归的搜索node的左右两个子树。

为了保证栈中存储的是根节点到当前遍历节点的路径，左右子树搜索完成后，将node从栈中弹出。

在主函数lowestCommonAncestor中，定义存储p、q路径的vector，p_path和q_path。定义求节点路径时使用的栈stack。

这里要说明的是，因为需要将栈中的内容赋值给p_path和q_path，所以我们使用vector来实现栈。

调用dfs求出p和q的路径，在完成p路径的搜索时，需要将stack清空，再用其寻找q节点路径。完成路径的计算后，设置指针common存储两节点的最近公共祖先。

然后进入while循环，遍历两个节点的路径，在循环中，寻找两条路径上最后一个相同的节点，将它存储至common，最后函数返回common。

那么到这里，二叉树中两节点的最近公共祖先就讲完了，感谢大家的观看，我们下节课再会。