【怒刷力扣】二叉树的公共祖先类题目，搞懂搜索整棵树和搜索单条边的区别，轻松手撕算法题

用户11598978

发布于 2025-12-18 20:41:05

文章被收录于专栏：码力up码力up

👨‍💻程序员三明治：个人主页 🔥 个人专栏: 《设计模式精解》《重学数据结构》

🤞先做到再看见！

236. 二叉树的最近公共祖先

题目

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

思路

这题肯定是用递归，然后最好是从下到上，那也就是后序遍历（左右中）

递归的返回值和参数

要有返回值，如果遇到p或者q，就把q或者p返回

递归的终止条件

遇到了空节点就返回null；或者遇到p或者q，就返回p或者q

单层递归的逻辑

递归顺序是左右中，在判断“中”的时候会有4种情况，第一种是left和right都为空，那就返回null，第二种是left为空，right不为空，那就返回right；第三种是left不为空right为kong，那就返回left；第四种是left和right都不为空，那就返回root

下面我们来看一个图解遍历的示例：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == q || root == p) {
            return root;
        }
        // 后序遍历
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //中
        if (left == null && right == null) {
            return null;
        } else if (left != null && right == null) {
            return left;
        } else if (left == null && right != null) {
            return right;
        } else {
            return root;
        }
    }
}

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

题目

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

思路

本题还是递归，因为是搜索树，所以左中右是有序的，不需要从下到上，从上到下就ok

递归的返回值和参数

返回值是要返回最近公共祖先，所以是TreeNode。

递归的终止条件

如果遇到root.val>p.val && root.val <q.val那说明root就是公共祖先

单层递归的逻辑

如果root.val<p.val && root.val < q.val 说明应该继续去右边找，因为不需要拿到递归的值再做判断，所以可以直接return dfs(root.left)。所以说这道题是搜索一条边而不是整棵树。

搜索一条边和搜索整棵树有什么区别？

搜索一条边的写法：

if (递归函数(root->left)) return ; if (递归函数(root->right)) return ;

搜索整个树写法：

left = 递归函数(root->left); right = 递归函数(root->right); left与right的逻辑处理;

否则去左边

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root.val > p.val && root.val < q.val) {
            return root;
        }
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        return root;
    }
}

如果我的内容对你有帮助，请辛苦动动您的手指为我点赞，评论，收藏。感谢大家!!

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-03，如有侵权请联系 cloudcommunity@tencent.com 删除

算法