坚持刷题｜二叉树的最近公共祖先

文章目录

题目
考察点
代码实现
实现总结
为什么不用迭代的方法实现？
二叉搜索树的最近公共祖先

Hello，大家好，我是阿月。坚持刷题，老年痴呆追不上我，今天刷：二叉树的最近公共祖先

题目

236.二叉树的最近公共祖先
在这里插入图片描述

考察点

对二叉树的理解：理解二叉树的基本概念，包括节点、左右子树等。
递归的理解和应用：解决这个问题的常用方法是使用递归。
最近公共祖先的概念：理解最近公共祖先的概念，即两个节点在树中的最低公共祖先节点。
时间复杂度和空间复杂度分析：能够分析算法的时间复杂度和空间复杂度，以及是否能够优化算法。

代码实现

public class LowestCommonAncestor {

    /**
     * 寻找二叉树中两个节点的最近公共祖先
     * @param root 二叉树的根节点
     * @param p 第一个节点
     * @param q 第二个节点
     * @return 最近公共祖先节点
     */
    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;
    }

    public static void main(String[] args) {
        LowestCommonAncestor solution = new LowestCommonAncestor();

        // 创建一个二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        TreeNode p = root.left;
        TreeNode q = root.right;

        TreeNode result = solution.lowestCommonAncestor(root, p, q);
        System.out.println("最近公共祖先: " + result.val);
    }
}

实现总结

寻找二叉树的公共祖先，是一种自底向上的寻找，而二叉树的回溯过程就是自底向上。
后序遍历（左右中）是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。
递归
- 递归函数返回值以及参数：
  - 返回值：递归函数返回的是最近公共祖先节点。
  - 参数：递归函数的参数包括当前节点 root，以及要查找的两个目标节点 p 和 q。
- 终止条件：
  - 如果当前节点为空 (root == null)，或者当前节点等于 p 或 q，则直接返回当前节点，因为当前节点就是其中一个目标节点的最近公共祖先。
- 单层递归逻辑：
  - 在每一层递归中，首先向左子树和右子树递归查找目标节点 p 和 q。
  - 如果左子树和右子树都找到了目标节点，则当前节点就是最近公共祖先。
  - 如果只有左子树找到了目标节点，则返回左子树的结果。
  - 如果只有右子树找到了目标节点，则返回右子树的结果。
- 在递归函数有返回值的情况下：
  - 如果要搜索一条边，递归函数返回值不为空的时候，立刻返回。
  - 如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。
时间复杂度：O(N)。
- 对于每个节点，都要做一些固定的工作：检查它是否等于目标节点 p 或 q，然后向下递归左右子树。因此，时间复杂度可以表示为 O(N)，其中 N 是二叉树中节点的数量。
- 在最坏的情况下，需要遍历整个二叉树才能找到最近公共祖先节点。因此，时间复杂度是线性的，与二叉树中的节点数量成正比。