236 二叉树的最近公共祖先

一、题目

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

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

二、题解

思路：DFS / 递归 / 二叉树

1. 核心思路

这道题可以使用递归来解决。

对于当前节点 root：

  • 如果 root 是 null，说明当前子树中没有找到 p 或 q；
  • 如果 root 等于 p 或 q，说明找到了其中一个目标节点，直接返回 root；
  • 然后分别去左子树和右子树中查找 p 和 q。

如果左右子树都找到了目标节点，说明 p 和 q 分别在当前节点的两侧，那么当前节点 root 就是最近公共祖先。

如果只有一边找到了，说明最近公共祖先在那一边，直接返回那一边的结果。

2. 具体步骤

  1. 如果当前节点 root == null，直接返回 null。
  2. 如果当前节点就是 p 或 q，直接返回当前节点。
  3. 递归查找左子树，得到 left。
  4. 递归查找右子树，得到 right。
  5. 如果 left 和 right 都不为空，说明 p 和 q 分别在左右子树中，当前节点就是最近公共祖先。
  6. 如果只有一边不为空，就返回不为空的那一边。
  7. 如果两边都为空，返回 null。

3. 关键逻辑

  • 如果 root == null，说明当前子树没有找到目标节点，返回 null。
  • 如果 root == p || root == q，说明当前节点就是目标节点，返回当前节点。
  • 如果 left != null && right != null，说明 p 和 q 分别在当前节点的左右子树中，因此当前节点就是最近公共祖先。
  • 如果只有 left 不为空，说明答案在左子树中，返回 left。
  • 如果只有 right 不为空，说明答案在右子树中，返回 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) {
        // 1. 处理特殊情况
        // 如果当前节点为空，说明没有找到 p 或 q
        if (root == null) {
            return null;
        }

        // 如果当前节点就是 p 或 q，直接返回当前节点
        // 因为一个节点可以是它自己的祖先
        if (root == p || root == q) {
            return root;
        }

        // 2. 定义变量
        // 在左子树中查找 p 和 q
        TreeNode left = lowestCommonAncestor(root.left, p, q);

        // 在右子树中查找 p 和 q
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 3. 核心逻辑
        // 如果左右子树都找到了目标节点
        // 说明 p 和 q 分别在当前节点的左右两侧
        // 当前节点 root 就是最近公共祖先
        if (left != null && right != null) {
            return root;
        }

        // 4. 返回结果
        // 如果左子树找到了，就返回 left
        // 如果右子树找到了，就返回 right
        // 如果都没找到，就返回 null
        return left != null ? left : right;
    }
}

四、复杂度分析

时间复杂度：O(n)O(n)

说明：其中 n 是二叉树中的节点数量。最坏情况下，需要遍历整棵二叉树。

空间复杂度：O(h)O(h)

说明：其中 h 是二叉树的高度。递归调用栈的深度最多为树的高度。

如果二叉树是平衡的，空间复杂度为 O(log⁡n)O(\log n)。

如果二叉树退化成链表，空间复杂度为 O(n)O(n)。

评论