一、题目
- 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
- 百度百科中最近公共祖先的定义为：
对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
二、示例
2.1> 示例 1:
【输入】 root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
【输出】 6
【解释】 节点 2 和节点 8 的最近公共祖先是 6。
2.2> 示例 2:
【输入】 root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
【输出】 2
【解释】 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明：
- 所有节点的值都是唯一的。
p、q为不同节点且均存在于给定的二叉搜索树中。
三、解题思路
- 根据题目描述，我们给我们两个节点
TreeNode p和TreeNode q，然后在二叉搜索树中去寻找最近公共祖先。那么题目中给出了非常关键的一个信息就是——二叉搜索树，那么这种二叉树具有如下的特征：
【若它的左子树不空】则
左子树上所有结点的值均小于它的根结点的值；【若它的右子树不空】则
右子树上所有结点的值均大于它的根结点的值；
- 所以针对如上特点，我们可以根据
TreeNode p和TreeNode q这两个树节点处于二叉搜索树不同位置来总结出如下的3种情况：
- 根据上图描述，我们可以得出如下3种情况：
【情况1】当
根节点的值处于p节点的值和q节点的值之间时，那么根节点就是最近公共祖先节点。【情况2】当
根节点的值大于p节点的值和q节点的值时，那么我们只需要遍历根节点的左子树，然后第一个遍历到的节点就是最近公共祖先节点。【情况3】当
根节点的值小于p节点的值和q节点的值时，那么我们只需要遍历根节点的右子树，然后第一个遍历到的节点就是最近公共祖先节点。【注意】每当遍历到一个子树的根节点时，都需要对比上面的3种情况，来决定执行那块逻辑。
- 上面就是具体的解题思路了，下面我们以
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4为例，看一下具体的处理过程。请见下图所示：
四、代码实现
classSolution { publicTreeNodelowestCommonAncestor(TreeNoderoot, TreeNodep, TreeNodeq) { if (root==null) returnnull; if (root.val<p.val&&root.val<q.val) returnlowestCommonAncestor(root.right, p, q); if (root.val>p.val&&root.val>q.val) returnlowestCommonAncestor(root.left, p, q); returnroot; } }
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」
