求解二叉树中两个节点的最近公共祖先节点
🌙
手机阅读
本文目录结构
求解二叉树中两个节点的最近公共祖先节点
求解二叉树中的两个节点的最近公共祖先节点可以分为三种情况来考虑
（1）该二叉树为搜索二叉树
解决办法，首先从根节点开始遍历。如果根节点的值比两个节点的值都大的情况下，则说明两个节点的共同祖先存在于
根节点的左子树中，因此递归遍历左子树。反之，则遍历右子树。当当前节点的值比其中一个节点的值大，比其中一个
节点的值小时，该节点则为两个节点的最近公共祖先节点。
（2）该二叉树为普通二叉树，但是每个节点含有指向父节点的指针。
通过指向父节点的指针，我们可以通过节点得到它的所有父节点，该父节点列表可以看做是一个链表，因此求两个节点
的最近公共祖先节点就可以看做是求两个链表的最近公共节点，以此来找到两个节点的最近公共祖先节点。
（3）该二叉树为普通二叉树，节点不含有指向父节点的指针。
这种情况下，我们可以从根节点出发，分别得到根节点到两个节点的路径。然后遍历两条路径，直到遇到第一个不相同
的节点为止，这个时候该节点前面的那个节点则为两个节点的最近公共祖先节点。
详细资料可以参考： 《二叉树中两个节点的最近公共祖先节点》
更多面试题
如果你想了解更多的前端面试题，可以查看本站的WEB前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题，也有一些大公司的面试图，可以让你面试更加顺利。
| 面试题 | ||
|---|---|---|
| HTML | CSS | JavaScript |
| jQuery | Vue.js | React |
| 算法 | HTTP | Babel |
| BootStrap | Electron | Gulp |
| Node.js | 前端经验相关 | 前端综合 |
| Webpack | 微信小程序 | - |
这些题库还在更新中，如果你有不错的面试题库欢迎分享给我，我整理后放上来；人人为我，我为人人，互帮互助，共同提高，祝大家都拿到心仪的Offer！
