首先我们补充说明一下什么是二叉搜索树：
在二叉搜索树中，对于每一个节点来说，他的左子树中的值都比他小，右子树的中的值都比他大。所以二叉搜索树的中序遍历是一组有序的数据。
对于上述这棵树，假设要求 p q 的最近公共祖先。
那么它有以下情况：
对于普通的二叉树来说，也无非就这几种情况：pq都在左，pq都在右，pq一左一右，pq有一个是根节点。
所以分别递归的去左子树和右子树中找 p q 节点的公共祖先，找到了则返回该节点，没有找到则返回空。
根据上述思路，我们很容易写出代码
思路二：假设该树是用孩子双亲表示法每个节点会保存它父亲节点的地址，可以层层网上找，直到找到两链表的第一个交点，该交点就是他们的公共祖先。
而对于普通的二叉树来说，只能层层往下找，不能往上，所以要保留两节点的路径，直到两路径的最后一个相同节点。这里我们用栈来保留两个节点的路径。
先弹出元素多的栈中的元素，然后两个栈再一起弹出，直到要弹出的节点相等，就是其最近公共祖先。
那么这里最大的难点就是存储路径。
这里用栈来存储路径，当遍历到一个节点时，将该节点放入栈中，再递归该节点的左树和右树找，如果找到了则保留路径，没找到则弹出。
假设找下图的p:
先将根节点放入栈，递归root节点的左子树找，找不到则弹出，在右子树中找。
当 root 走到 6 的时候，发现该节点的左右均为空，说明在该子树中没找到目标节点，弹出 6 ，在 5 的右子树中继续找。
同理在 5 的右子树中也找不到，会弹出直到去 3 的右子树找，来到 1 ，找到。
到此这篇关于Java 图文并茂讲解两种找二叉树的最近公共祖先的方法的文章就介绍到这了,更多相关Java 二叉树最近公共祖先内容请搜索七叶笔记以前的文章或继续浏览下面的相关文章希望大家以后多多支持七叶笔记！
