LeetCode236.最近的公共祖先

电玩女神 2023-09-25 21:27 46阅读 0赞

![在这里插入图片描述][fcc7f7a044d24cf892746081a0dc16ac.png]

# 求解最近公共祖先的算法 #

分为两个步骤：

1.  求出两节点路径
2.  取两路径上最后一个相同的节点（该节点即为p，q节点的最近公共祖先）

# 节点路径的算法设计与实现 #

求节点路径即输入二叉树根节点与待求节点返回根节点到该节点路径上的所有节点。

具体有如下几个要点：

1.  我们需要设置一个栈，存储最终的节点路径。找到该节点时，从栈底到栈顶存储的节点即为从根节点到该节点的路径。  
    ![在这里插入图片描述][09198bd64fcf457692cbfae7f6df7301.png]
2.  需要通过遍历算法，从根节点遍历至该节点。树的遍历算法可以是递归的深度优先搜索算法。找到该节点后就结束搜索。  
    ![在这里插入图片描述][cc9101ecea4b497db7a760210dca9d0f.png]
3.  将遍历过程中遇到的节点按照顺序存储到栈中。节点遍历完成之后需要弹出栈，从而保证栈中存储的节点时根节点到当前遍历节点路径上的节点。  
    ![在这里插入图片描述][b9b26852449543cabc08c1c4a499de9a.png]  
    ![在这里插入图片描述][b3deca2ec7494a7bb19da7b44bb6f335.png]  
    ![在这里插入图片描述][d2c4b65ee97f4a6b9a122d582ed7654d.png]

# 具体代码 #

## 深度优先搜索寻找路径上的节点 ##

![在这里插入图片描述][30ab16ba645b4fa295425cdf9fa2c7df.png]

## 利用两节点的路径寻找最近公共祖先 ##

![在这里插入图片描述][86865819f7024f53ac3dab1eb94d106c.png]  
![在这里插入图片描述][a4abff1d98314f2390861786ab243197.png]

## 测试主程序 ##

![在这里插入图片描述][9a4b8995d01d445499b6cd89cee31af3.png]  
![在这里插入图片描述][677ba15bc9b5485b92b192b134c7b006.png]  
**参考资料**：  
[算法与数据结构，二叉树，程序员面试高频题，最近的公共祖先][Link 1]

[fcc7f7a044d24cf892746081a0dc16ac.png]: https://img-blog.csdnimg.cn/fcc7f7a044d24cf892746081a0dc16ac.png
[09198bd64fcf457692cbfae7f6df7301.png]: https://img-blog.csdnimg.cn/09198bd64fcf457692cbfae7f6df7301.png
[cc9101ecea4b497db7a760210dca9d0f.png]: https://img-blog.csdnimg.cn/cc9101ecea4b497db7a760210dca9d0f.png
[b9b26852449543cabc08c1c4a499de9a.png]: https://img-blog.csdnimg.cn/b9b26852449543cabc08c1c4a499de9a.png
[b3deca2ec7494a7bb19da7b44bb6f335.png]: https://img-blog.csdnimg.cn/b3deca2ec7494a7bb19da7b44bb6f335.png
[d2c4b65ee97f4a6b9a122d582ed7654d.png]: https://img-blog.csdnimg.cn/d2c4b65ee97f4a6b9a122d582ed7654d.png
[30ab16ba645b4fa295425cdf9fa2c7df.png]: https://img-blog.csdnimg.cn/30ab16ba645b4fa295425cdf9fa2c7df.png
[86865819f7024f53ac3dab1eb94d106c.png]: https://img-blog.csdnimg.cn/86865819f7024f53ac3dab1eb94d106c.png
[a4abff1d98314f2390861786ab243197.png]: https://img-blog.csdnimg.cn/a4abff1d98314f2390861786ab243197.png
[9a4b8995d01d445499b6cd89cee31af3.png]: https://img-blog.csdnimg.cn/9a4b8995d01d445499b6cd89cee31af3.png
[677ba15bc9b5485b92b192b134c7b006.png]: https://img-blog.csdnimg.cn/677ba15bc9b5485b92b192b134c7b006.png
[Link 1]: https://www.bilibili.com/video/BV12Z4y15721/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb