865.具有所有最深节点的最小子树：深度优先搜索（一次DFS + Python5行）

【LetMeFly】865.具有所有最深节点的最小子树：深度优先搜索（一次DFS + Python5行）

力扣题目链接：https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/

给定一个根为 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-cn.com/problems/lowest-common-ancestor-of-deepest-leaves

解题方法：DFS

思考对于根节点root，答案是什么：

• 如果左子树比右子树深，说明答案一定在左子树上
• 如果右子树比左子树深，说明答案一定在右子树上
• 如果左右子树一样深，说明root就是答案

当左子树（假设为left节点）比右子树深时，答案是哪个呢？

答案是以left为节点时“含所有最深节点最小子树”的答案。

好一个天然递归。递归时候都需要什么？

1. 树的深度
2. 答案节点

以上。

• 时间复杂度$O(size(root))$
• 空间复杂度$O(depth(root))$

AC代码

C++

/*
 * @LastEditTime: 2026-01-09 13:19:41
 */
typedef pair<TreeNode*, int> result;
class Solution {
private:
    result dfs(TreeNode* root) {
        result left = root->left ? dfs(root->left) : result{nullptr, 0};
        result right = root->right ? dfs(root->right) : result{nullptr, 0};
        TreeNode* node = left.second == right.second ? root : (left.second > right.second ? left.first : right.first);
        return {node, max(left.second, right.second) + 1};
    }
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).first;
    }
};

Python

'''
LastEditTime: 2026-01-09 20:58:21
'''
from typing import Optional, Tuple

empty_result = (None, 0)

class Solution:
    def dfs(self, root: TreeNode) -> Tuple[Optional[TreeNode], int]:
        left = self.dfs(root.left) if root.left else empty_result
        right = self.dfs(root.right) if root.right else empty_result
        return [root if left[1] == right[1] else left[0] if left[1] > right[1] else right[0], max(left[1], right[1]) + 1]

    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        return self.dfs(root)[0]

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源