剑指 Offer 68 - II: 二叉树的最近公共祖先

[songyy5517]

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

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

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

示例 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。因为根据定义最近公共祖先节点可以为节点本身。

分析 这道题需要我们求二叉树中两节点的最近祖先。我们可以基于后序遍历（DFS）对整棵树进行递归遍历，遇到空节点返回null，遇到o1或o2返回对应的节点。因此，对应某个节点，其左右子树一共存在三种情况。

1. 左右都不为空，此时当前节点即为最近祖先节点，返回该该节点（将该祖先节点向上传递）；
2. 左为空，右不为空。此时，两个节点都在右子树中，返回右子树中的节点。
3. 左不为空，右为空。则与2相反。

最后返回到达根节点的节点值。

[songyy5517]

思路：递归后序遍历，自底向上返回公共祖先节点

1. 异常处理/递归出口：当节点为空/p/q时，返回当前节点；
2. 分别递归遍历左右子树，得到对应返回的两个节点left, right；
   • 若返回的节点为空，则说明当前节点的对应子树中不包含指定节点（p/q）；若不为空，则包含指定节点，且返回值就是该节点。
3. 通过left和right判断最小公共祖先并返回： （1）若left和right都不为空，则指定节点分别位于左右子树中，最小公共祖先为当前节点root。 （2）若left为空，right不为空，则两个指定节点都在右子树中，最小公共祖先为right；反之亦然。 （3）若都为空，则最小公共祖先不在以当前节点为根的子树中；
4. 返回最小公共祖先。

复杂度分析

• 时间复杂度： $O(N)$ ，遍历整个二叉树需要花费 $O(N)$ 的时间， $N$ 为二叉树的节点个数；
• 空间复杂度： $O(N)$ ，最坏情况下二叉树退化成链表，递归深度为 $N$ ，系统需要使用 $O(N)$ 大小的栈空间。

[songyy5517]

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        // 1. 异常处理
        if (root == null)
            return -1;

        // 2. 后序遍历，返回最近祖先
        return postOrder(root, o1, o2).val;
    }

    TreeNode postOrder(TreeNode root, int o1, int o2){
        // 1. 递归出口
        if (root == null || root.val == o1 || root.val == o2)
            return root;

        // 2. 后序遍历
        TreeNode left = postOrder(root.left, o1, o2);
        TreeNode right = postOrder(root.right, o1, o2);

        if (left != null && right != null)
            return root;

        return left == null ? right : left;
    }
}

[songyy5517]

Key points:

• 若方法的形参与主方法相同，考虑是否可以合并。

2024/2/1 2024/6/5