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

短命女 2024-03-22 20:46 64阅读 0赞

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

### 题目 ###

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

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

**示例 1：**  
![90238827ec8d4f2bf25f7c29018acf69.png][]

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 
    输出：3 
    解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

**示例 2：**  
![25942078459688fd564e6176ebeff3d9.png][]

输入：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

**提示：**

*  树中节点数目在范围  \[ 2 , 1 0 5 \] \[2, 10^5\] \[2,105\] 内。
 *   − 1 0 9 < = N o d e . v a l < = 1 0 9 -10^9 <= Node.val <= 10^9 −109<=Node.val<=109
 *  所有  N o d e . v a l Node.val Node.val 互不相同 。
 *  p != q
 *  p 和 q 均存在于给定的二叉树中。

--------------------

### 题解 ###

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

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

1.  根节点就是 `节点p`。
2.  左子树包含 `节点p`。
3.  右子树包含 `节点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`，其中：

1.   h a s \[ 0 \] = = t r u e has\[0\] == true has\[0\]==true 表示包含 `节点p`， h a s \[ 0 \] = = f a l s e has\[0\] == false has\[0\]==false 表示不包含。
2.   h a s \[ 1 \] = = t r u e has\[1\] == true has\[1\]==true 表示包含 `节点q`， h a s \[ 1 \] = = f a l s e has\[1\] == false has\[1\]==false 表示不包含。

改进后的代码实现为：

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
      
    }

### 复杂度分析 ###

**时间复杂度：** O ( N ) O(N) O(N)，`N` 为二叉树中节点的个数，每个节点都需要遍历一次。

**空间复杂度：** O ( N ) O(N) O(N)，`N` 为二叉树中节点的个数，空间复杂度取决于递归调用栈的深度，最大为 `N`。

[90238827ec8d4f2bf25f7c29018acf69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/549318c7095f418c848796cf768e6846.png
[25942078459688fd564e6176ebeff3d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a2c7259864fa481a84db79116290fc8b.png