如何优雅地找到二叉树的最近公共祖先

在这里插入图片描述

核心思路

从根节点开始,向左右子树递归搜索目标节点,然后根据左右子树的返回结果判断最近公共祖先的位置。

1.递归终止条件

1
2
3


if (root == null || root == p || root == q) {
    return root;
}

如果搜索到了空节点,说明这条路径上没有找到目标节点；

如果当前节点就是我们要找的节点之一,直接返回。

2.向左右子树递归搜索

1
2


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

分别在左子树和右子树中搜索 p 和 q。

3.根据搜索结果判断

(1) p 和 q 分别在当前节点的左右两侧,那么当前节点 root 就是它们的最近公共祖先。

1
2
3


if (l != null && r != null) {
    return root;
}

(2)左右子树都返回 null,说明当前子树中既没有 p 也没有 q。

1
2
3


if (l == null && r == null) {
    return null;
}

(3)当 l 和 r 一个为空、一个不为空时,返回非空的那个结果。

1

return l != null ? l : r;

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        // 遇到空,或者p,或者q,直接返回
        return root;
    }
    
    TreeNode l = lowestCommonAncestor(root.left, p, q);
    TreeNode r = lowestCommonAncestor(root.right, p, q);
    
    if (l != null && r != null) {
        // 左树也搜到,右树也搜到,返回root
        return root;
    }
    
    if (l == null && r == null) {
        // 都没搜到返回空
        return null;
    }
    
    // l和r一个为空,一个不为空
    // 返回不空的那个
    return l != null ? l : r;
}

如果觉得有帮助，欢迎点赞、关注、转发~