前引：
树可以分为好几种：普通树，二叉树（二叉链，三叉链），二叉搜索树等等，今天我们，讨论的的问题可就和就几种树有关。
我们先易后难，讨论二叉搜索树！
且所有的输入满足
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的树中。
由于二叉搜索树是有序的，左子树全部小于根节点，右子树全部大于根节点。
倘若我们要查找p,q节点的公共祖先。其中根节点的值等于p节点的值或者等于q节点的值，根就是我们要查找的公共祖先。
例如：p为5，q为2；当我们查找到2的时候，就可以停止；由于我们从树根节点遍历下来，且p,q节点均存在于树中，我们就可以认为p一定存在于q的子树中。
当根节点的值大于p和q的值时，我们就可以只遍历左子树， 同样，当根节点的值小于p和q的值时，我们就可以只遍历右子树；
倘若一个比根节点的值大，一个比根节点的值要小，则肯定一个在左子树，一个在右子树，当前根节点就是我们要找的最近公共祖先 。
- 当根节点的值大于p和q的值时，我们就可以只遍历左子树
- 当根节点的值小于p和q的值时，我们就可以只遍历右子树；
- 否则，当前根节点就是我们要找的最近公共祖先 。
下面看我们的代码实现：
什么是三叉链结构呢？
就是每个子结点都有一个指针，指向父节点。
所以三叉链结构，解决这个问题十分简单。我们只需要在树中找到对应的节点，在通过指向父节点的指针找到最近公共祖先。其实，这有点在两个链表中寻找公共节点的意思。
由于题库中没有找到这个题，代码就不实现了。
二叉树和普通树都没有什么特点，所以我们只需要遍历树中的每个节点，倘若我们要查找p,q节点的公共祖先。其中根节点的值等于p节点的值或者等于q节点的值，根就是我们要查找的公共祖先。倘若一个比根节点的值大，一个比根节点的值要小，则肯定一个在左子树，一个在右子树，当前根节点就是我们要找的最近公共祖先 。
到这里，我们本文所讲的寻找公共祖先篇已经结束了。
但是在最后一普通树、二叉树一篇中，我们可以看一下时间复杂度是多少呢？ O（N）？其实我们遍历一棵树，时间复杂度也就是O（N）；但是我们做了许多重复的工作？
我们再看一下这张图：
比如我们要查找的节点为7 和4；我们首先判断以3为根节点的树，遍历完左子树和右子树，发现全在左子树；在判断以5为根节点的树，遍历完左子树和右子树，发现全在右子树。（其实到这里我们已经发现了，6 2 7 4 我们已经遍历了两遍） 直到我们找到7和4.
由于做了重复的工作 第一个N第二次N/2。。。。。。我们可以认为是N^2了。
那可以改善吗？
我们可以借鉴三叉链方法：空间换时间，用容器将路径保存，再寻找最近的公共节点。
下面给出代码实现：
效率有所提高的代码实现：
本篇博文到这里就结束了，谢谢大家的观看！
你们的 【三连】 是给Qyuan最大的肯定！
↓ ↓ ↓
注：如果本篇博客有任何错误和建议，欢迎伙伴们留言，你快说句话啊！
如果需要练习的小伙伴，可以打开下方链接：
二叉搜索树的最近公共祖先
https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
二叉树的最近公共祖先：
本文地址：http://nhjcxspj.xhstdz.com/quote/3488.html 物流园资讯网 http://nhjcxspj.xhstdz.com/ , 查看更多