当前位置：首页 > article >正文

leetcode hot100【LeetCode 236.二叉树的最近公共祖先】java实现

article 2024/11/17 5:09:06

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

题目描述

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

节点可以表示为它在树中的路径，其中路径的第一个节点是根节点，每个后续节点是其父节点的直接子节点。

示例 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 = 2, q = 0
输出: 1
解释: 节点 2 和 0 的最近公共祖先是 1，因为 0 是 2 的父节点。

Java 实现代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }
}

解题思路

递归法:

从根节点开始递归搜索。
如果当前节点为 null，返回 null。
如果当前节点为 p 或 q，返回当前节点。
递归搜索左右子树：
如果左右子树都能找到目标节点，则当前节点为最近公共祖先。
如果只有一侧子树能找到目标节点，则返回该子树的结果。

复杂度分析

时间复杂度：O(n)，其中 n 是树中的节点数。在最坏的情况下，我们需要访问树中的每个节点。
空间复杂度：O(h)，其中 h 是树的高度。这是因为在递归过程中，我们可能会有多达 h 层的函数调用栈，这发生在树完全不平衡时，所有节点都在一个单独的链上。

示例树结构:
    3
   / \
  5   1
 / \  / \
6  2 0  8
  / \
 7   4 ```
输入: p = 4, q = 8

递归执行过程:

根节点 3

检查当前节点是否为 null、p 或 q。3 不是 4 或 8。
递归左子树 root.left = 5。

节点 5

检查当前节点是否为 null、p 或 q。5 不是 4 或 8。
递归左子树 root.left = 6。

节点 6

检查当前节点是否为 null、p 或 q。6 不是 4 或 8。
递归左子树 root.left = null，返回 null。
递归右子树 root.right = null，返回 null。
左右子树返回均为 null，返回 null。

返回节点 5，递归右子树 root.right = 2。

节点 2

检查当前节点是否为 null、p 或 q。2 不是 4 或 8。
递归左子树 root.left = 7。

节点 7

检查当前节点是否为 null、p 或 q。7 不是 4 或 8。
递归左子树 root.left = null，返回 null。
递归右子树 root.right = null，返回 null。
左右子树返回均为 null，返回 null。

返回节点 2，递归右子树 root.right = 4。

节点 4

当前节点为 p = 4，直接返回当前节点 4。

返回节点 2，左子树返回 null，右子树返回 4，返回 4。

返回节点 5，左子树返回 null，右子树返回 4，返回 4。

返回节点 3，递归右子树 root.right = 1。

节点 1

检查当前节点是否为 null、p 或 q。1 不是 4 或 8。
递归左子树 root.left = 0。

节点 0

检查当前节点是否为 null、p 或 q。0 不是 4 或 8。
递归左子树 root.left = null，返回 null。
递归右子树 root.right = null，返回 null。
返回 null。

返回节点 1，递归右子树 root.right = 8。

节点 8

当前节点为 q = 8，直接返回当前节点 8。

返回节点 1，左子树返回 null，右子树返回 8，返回 8。

返回节点 3，左子树返回 4，右子树返回 8。

左右子树均非 null，所以 3 是最近公共祖先。

结果: p = 4 和 q = 8 的最近公共祖先是 3。