【力扣题解】P236-二叉树的最近公共祖先-Java题解

花无缺

👨‍💻博客主页：@花无缺
欢迎点赞👍 收藏⭐ 留言📝 加关注✅!
本文由 花无缺 原创

收录于专栏【力扣题解】

文章目录

【力扣题解】P236-二叉树的最近公共祖先-Java题解
- 🌏题目描述
- 💡题解
- 🌏总结

【力扣题解】P236-二叉树的最近公共祖先-Java题解

P236-二叉树的最近公共祖先

🌏题目描述

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

百度百科中最近公共祖先的定义为：“对于有根树 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 。

示例 2：

在这里插入图片描述

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

💡题解

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 空树, 返回 null
    // 当前节点是 p 节点, 那么直接返回 p, 说明 p 就是 p, q 的祖先节点
    // 当前节点是 q 节点, 那么直接返回 q, 说明 q 就是 p, q 的祖先节点
    if (root == null || root == p || root == q) {
        return root;
    }
    // 递归遍历左子树和右子树
    // 搜索左子树和右子树中是否有 p 或 q
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 如果左右子树的搜索结果都不为空, 说明 p 和 q 都在左右子树中找到了
    // 当前节点肯定就是 p, q 的祖先节点, 直接返回 root
    if (left != null && right != null) {
        return root;
    }
    // 如果 left 为空, right 不为空, 那么祖先节点就在右子树中
    // 结果就是 right, 直接返回
    if (left == null && right != null) {
        return right;
    //     如果 left 不为空, right 为空, 那么祖先节点就在左子树中
    //     直接返回 left
    } else if (left != null && right == null) {
        return left;
    //     否则 left 和 right 都为空
    //     说明没有找到公共祖先, 返回 null
    } else {
        return null;
    }
}

时间复杂度：O(n)，要搜索整个二叉树，遍历所有节点，节点数为 n。

🌏总结

这个题目要求我们查找两个节点的最近公共祖先节点，那么我们肯定需要自底向上的搜索节点，因为只有自底向上的搜索才会找到两个节点最近的公共祖先节点，那么我们就想到了回溯，先遍历最底层的节点，如果不满足条件，再回溯到上层的节点查找，那么我们就可以使用后序遍历（左右中），后序遍历就是很自然的回溯过程。

此处我们使用的是递归的写法，那么递归的终止条件如何确定呢？首先假设我们从根节点开始出发，如果当前节点是空节点，说明这是一棵空树，那么递归肯定要终止，并且返回 null。另外，如果根节点就是 p 节点或者 q 节点，那么 p 和 q 的公共祖先节点就是根节点，因为如果根节点就是 p（q），那么另外一个节点 q（p）肯定就是当前节点（根节点）的子节点，所以根节点就是公共祖先节点。

所以递归的终止条件为：

// 空树, 直接返回 null
if (root == null) {
    return null;
}
// 当前节点是 p 节点, 那么直接返回 p, 说明 p 就是 p, q 的祖先节点
// 当前节点是 q 节点, 那么直接返回 q, 说明 q 就是 p, q 的祖先节点
if (root == p || root == q) {
    return root;
}

接下来我们就要进行后序遍历了，先遍历左子树，再遍历右子树：

而且我们要将左右子树递归的结果保存下来，因为在回溯到中间节点的时候，我们需要使用左右子树递归的结果。

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

然后遍历中间节点：

如果说左右子树返回的结果都不为空，那么说明左右子树都分别找到了 p 和 q 节点，那么说明当前节点就是他们的最近公共祖先节点。

如果有一个子树的结果为空，那么说明他们的祖先节点就在另一棵子树，那么直接返回另一棵子树的结果。

如果两棵树都为空，那么说明搜索完了整棵树都没有找到符合题意的公共祖先，直接返回 null；

// 如果 left 为空, right 不为空, 那么祖先节点就在右子树中
// 结果就是 right, 直接返回
if (left == null && right != null) {
    return right;
//     如果 left 不为空, right 为空, 那么祖先节点就在左子树中
//     直接返回 left
} else if (left != null && right == null) {
    return left;
//     否则 left 和 right 都为空
//     说明没有找到公共祖先, 返回 null
} else {
    return null;
}