LeetCode 题解工作台
具有所有最深节点的最小子树
给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。 返回包含原始树中所有 最深节点 的 最小子树 。 如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。 一个节点的 子树 是该节点加上它的所有后代的集合。 示例 1： 输入： root = [3,5…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们设计一个函数 ，返回以 为根的子树中，包含所有最深节点的最小子树，以及以 为根的子树的深度。 函数 的执行过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一个根为 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/problems/lowest-common-ancestor-of-deepest-leaves
解题思路
方法一：递归
我们设计一个函数 ，返回以 为根的子树中，包含所有最深节点的最小子树，以及以 为根的子树的深度。
函数 的执行过程如下：
- 如果 为空，返回 和 。
- 否则，递归计算 的左子树和右子树的最小子树以及深度，分别为 和 以及 和 。如果 ，则以 的左孩子为根的子树中包含所有最深节点的最小子树就是 ，深度为 ；如果 ，则以 的右孩子为根的子树中包含所有最深节点的最小子树就是 ，深度为 ；如果 ，则 就是包含所有最深节点的最小子树，深度为 。
最后，返回 的结果的第一个元素即可。
时间复杂度 ，空间复杂度 。其中 为二叉树的节点个数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(root: Optional[TreeNode]) -> Tuple[Optional[TreeNode], int]:
if root is None:
return None, 0
l, ld = dfs(root.left)
r, rd = dfs(root.right)
if ld > rd:
return l, ld + 1
if ld < rd:
return r, rd + 1
return root, ld + 1
return dfs(root)[0]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Test the candidate's ability to implement tree traversal algorithms like DFS.
- question_mark
Evaluate how well the candidate optimizes space usage during the process.
- question_mark
Check if the candidate correctly identifies the concept of common ancestors and subtree size.
常见陷阱
外企场景- error
Failing to correctly track the depth of nodes, leading to incorrect identification of the deepest nodes.
- error
Confusing the concept of subtree size with just the depth of nodes.
- error
Not properly handling edge cases like a tree with a single node or nodes with equal depths.
进阶变体
外企场景- arrow_right_alt
Finding the subtree for the deepest node given a weighted binary tree.
- arrow_right_alt
Handling unbalanced trees with varying depths across subtrees.
- arrow_right_alt
Modifying the problem to identify the smallest subtree containing a specific set of nodes.