二叉搜索树的最近公共祖先、二叉树的最近公共祖先

本文主要是介绍二叉搜索树的最近公共祖先、二叉树的最近公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

---

1. 二叉搜索树的最近公共祖先（力扣：235）
2. 二叉树的最近公共祖先（力扣：236）

二叉搜索树的最近公共祖先

题目

二叉搜索树的最近公共祖先（力扣：235）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

分析

利用二叉搜索树的特性，左子树节点都小于根节点，右子树节点都大于根节点。

1. 当两个子节点都大于根节点时，则在右子树查找。
2. 当两个子节点都小于根节点时，则在左侧查找。
3. 否则，找到了最近的公共祖先了。

代码实现

    /*** 235. 二叉搜索树的最近公共祖先* @param root* @param p* @param q* @return*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root.val > p.val && root.val >q.val){return lowestCommonAncestor(root.left, p, q);}if (root.val < p.val && root.val < q.val){return lowestCommonAncestor(root.right, p, q);}return root;}

二叉树的最近公共祖先

题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

分析

可以使用递归来实现：

1. 当root为null或者root等于两个节点中的一个时，返回root节点。
2. 递归获取左节点和右节点。
3. 当左节点和右节点都不为空时，代表指定的两个节点都在以root为根节点的树上，这时直接返回root即可。
4. 如果左节点或右节点中有一个不为null，则返回该节点。
5. 否则，代表左右节点中都没有要查找的节点，则返回null。

代码实现

    /*** 236. 二叉树的最近公共祖先* @param root* @param p* @param q* @return*/public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q){return root;}TreeNode left = lowestCommonAncestor2(root.left, p, q);TreeNode right = lowestCommonAncestor2(root.right, p, q);if (left != null && right != null){return root;}else if (left != null){return left;}else if (right != null){return right;}return null;}

这篇关于二叉搜索树的最近公共祖先、二叉树的最近公共祖先的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---