【算法题解】51. 二叉树的最近公共祖先

❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

❞

题目

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

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

示例 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 = 1, q = 2 
输出：1

提示：

树中节点数目在范围内。
所有互不相同。
p != q
p 和 q 均存在于给定的二叉树中。

题解

「公共祖先的定义」：以这个节点为根节点的二叉树中，同时包含有 节点p 和 节点q。

判断一颗树是否包含 节点p ，只要满足以下条件中的一个即可：

根节点就是 节点p。
左子树包含 节点p。
右子树包含 节点p。

很明显的可以看出条件2和3是这个问题的子问题，首先考虑递归的思路去实现。

以 「Java」 代码为例：

private boolean dfs(TreeNode node, TreeNode p){
    // 边界条件
    if(node == null){
        return false;
    }
    // 满足条件1
    if(node == p){
        return true;
    }
    // 满足 条件2 或 条件3
 return dfs(node.left) || dfs(node.right);
}

同样的，判断是否包含 节点q 也是上面的逻辑。

因为判定是否是公共祖先，需要同时判定是否包含 节点p 和 节点q，所以需要对上面的递归函数稍微改进一下。

我们可以让递归函数返回一个 boolean 数组 has[]来表示是否包含节点p 和 节点q，其中：

表示包含 节点p，表示不包含。
表示包含 节点q，表示不包含。

改进后的代码实现为：

private boolean[] dfs(TreeNode node, TreeNode p, TreeNode q){
    boolean[] has = new boolean[2];
    // 边界条件
    if(node == null){
        return hase;
    }

    // 满足条件1
    if(node == p){
        has[0] = true;
    }
    if(node == q){
        has[1] = true;
    }

    boolean[] leftHas = dfs(node.left, p, q);
    boolean[] rightHas = dfs(node.left, p, q);

    // 满足 条件2 或 条件3
    has[0] = has[0] || leftHas[0] || rightHas[0];
    has[1] = has[1] || leftHas[1] || rightHas[1];

    // 只要满足 has[0] 和 has[1] 都为true
    // 就说明这个节点 node 是节点 p 和 q 的公共祖先。
    
 return has;
}

通过上述递归函数我们可以求得 节点p 和 节点q 的所有公共祖先，但是题目要求的是求得 「最近公共祖先」。

「最近公共祖先的定义」：所有公共祖先当中，深度最大的那个即为最近公共祖先。

因为递归函数是从上往下递归的，答案的得出是从下往上回溯的。所以最先知道其是公共祖先的那个节点就是最近公共祖先。

假设答案为 ans，当知道节点 node 是公共祖先且 ans 为空的时候，节点 node 就是答案。因为 ans 不空的时候，node 已经不是最深处的那个公共祖先了。

完整代码见代码实现。

Java 代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode ans = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        dfs(root, p, q);
        
        return ans;
    }

    private boolean[] dfs(TreeNode node, TreeNode p, TreeNode q){
        boolean[] has = new boolean[2];
        // 边界条件
        if(node == null){
            return has;
        }

        // 满足条件1
        if(node == p){
            has[0] = true;
        }

        if(node == q){
            has[1] = true;
        }

        boolean[] leftHas = dfs(node.left, p, q);
        boolean[] rightHas = dfs(node.right, p, q);

        // 满足 条件2 或 条件3
        has[0] = has[0] || leftHas[0] || rightHas[0];
        has[1] = has[1] || leftHas[1] || rightHas[1];

        // 最先知道答案的即为最近公共祖先
        if(ans == null && has[0] && has[1]){
            ans = node;
        }

        
        return has;
    }

}

Go 代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {

    var ans *TreeNode

    var dfs func(node *TreeNode) []bool

    dfs = func(node *TreeNode) []bool {
        has := []bool{false, false}
        if node == nil {
            return has
        }
        if node == p {
            has[0] = true
        }
        if node == q {
            has[1] = true
        }

        leftHas := dfs(node.Left)
        rightHas := dfs(node.Right)

        has[0] = has[0] || leftHas[0] || rightHas[0]
        has[1] = has[1] || leftHas[1] || rightHas[1]

        if ans == nil && has[0] && has[1] {
            ans = node
        }

        return has
    }

    dfs(root)

    return ans
  
}