Medium

题目描述

给定一个二叉树的根节点 root，每个节点的深度是该节点到根节点的最短距离。

返回包含原始树中所有最深节点的最小子树。

如果一个节点在整棵树中具有最大的可能深度，那么该节点是最深的。

节点的子树是由该节点以及该节点的所有后代组成的树。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：我们返回值为 2 的节点，在图中用黄色标记。
图中用蓝色标记的节点是树中最深的节点。
注意，节点 5、3 和 2 都包含树中最深的节点，但节点 2 的子树最小，所以我们返回它。

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的节点是 2，有效的子树是节点 2、1 和 0 的子树，但节点 2 的子树是最小的。

提示：

  • 树中节点的数量将在 [1, 500] 范围内。
  • 0 <= Node.val <= 500
  • 树中节点的值是唯一的。

注意： 这个问题与 1123 题相同：https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/

解题思路

这道题要求找到包含所有最深节点的最小子树，本质上就是找最深叶子节点的最近公共祖先（LCA）。

解题思路：

  1. DFS + 高度计算：我们需要找到所有最深的叶子节点，然后找到它们的最近公共祖先。

  2. 核心观察：对于任意节点，如果它的左子树和右子树的最大深度相等，那么这个节点就是包含所有最深节点的最小子树的根。如果左右子树深度不同，那么答案在深度更大的那一侧。

  3. 算法步骤：

    • 递归计算每个节点的深度
    • 对于每个节点，比较左右子树的最大深度
    • 如果左右深度相等，当前节点就是答案
    • 如果不相等，递归到深度更大的子树中寻找答案

  4. 优化方案：可以在一次 DFS 中同时计算深度和找到答案节点，避免多次遍历。

推荐解法：使用 DFS 一次遍历同时计算深度和找答案，时间复杂度 O(n)，空间复杂度 O(h)，其中 h 是树的高度。

代码实现

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).second;
    }
    
private:
    pair<int, TreeNode*> dfs(TreeNode* node) {
        if (!node) return {0, nullptr};
        
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        
        int leftDepth = left.first;
        int rightDepth = right.first;
        
        if (leftDepth == rightDepth) {
            return {leftDepth + 1, node};
        } else if (leftDepth > rightDepth) {
            return {leftDepth + 1, left.second};
        } else {
            return {rightDepth + 1, right.second};
        }
    }
};

class Solution:
    def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node):
            if not node:
                return 0, None
            
            left_depth, left_lca = dfs(node.left)
            right_depth, right_lca = dfs(node.right)
            
            if left_depth == right_depth:
                return left_depth + 1, node
            elif left_depth > right_depth:
                return left_depth + 1, left_lca
            else:
                return right_depth + 1, right_lca
        
        return dfs(root)[1]

public class Solution {
    public TreeNode SubtreeWithAllDeepest(TreeNode root) {
        return DFS(root).Item2;
    }
    
    private (int, TreeNode) DFS(TreeNode node) {
        if (node == null) return (0, null);
        
        var left = DFS(node.left);
        var right = DFS(node.right);
        
        int leftDepth = left.Item1;
        int rightDepth = right.Item1;
        
        if (leftDepth == rightDepth) {
            return (leftDepth + 1, node);
        } else if (leftDepth > rightDepth) {
            return (leftDepth + 1, left.Item2);
        } else {
            return (rightDepth + 1, right.Item2);
        }
    }
}

var subtreeWithAllDeepest = function(root) {
    function dfs(node) {
        if (!node) return [null, 0];
        
        let [leftLCA, leftDepth] = dfs(node.left);
        let [rightLCA, rightDepth] = dfs(node.right);
        
        if (leftDepth > rightDepth) {
            return [leftLCA, leftDepth + 1];
        } else if (leftDepth < rightDepth) {
            return [rightLCA, rightDepth + 1];
        } else {
            return [node, leftDepth + 1];
        }
    }
    
    return dfs(root)[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历树中的每个节点一次
空间复杂度O(h)递归调用栈的深度，h 为树的高度，最坏情况下为 O(n)