LeetCode 题解工作台
移除子树后的二叉树高度
给你一棵 二叉树 的根节点 root ，树中有 n 个节点。每个节点都可以被分配一个从 1 到 n 且互不相同的值。另给你一个长度为 m 的数组 queries 。 你必须在树上执行 m 个 独立 的查询，其中第 i 个查询你需要执行以下操作： 从树中 移除 以 queries[i] 的值作为根节点…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
我们先通过一次 DFS 遍历的深度，存放在哈希表 中，其中 表示节点 的深度。 然后我们设计一个函数 $dfs(root, depth, rest)$，其中：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵 二叉树 的根节点 root ，树中有 n 个节点。每个节点都可以被分配一个从 1 到 n 且互不相同的值。另给你一个长度为 m 的数组 queries 。
你必须在树上执行 m 个 独立 的查询，其中第 i 个查询你需要执行以下操作：
- 从树中 移除 以
queries[i]的值作为根节点的子树。题目所用测试用例保证queries[i]不 等于根节点的值。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是执行第 i 个查询后树的高度。
注意：
- 查询之间是独立的，所以在每个查询执行后，树会回到其 初始 状态。
- 树的高度是从根到树中某个节点的 最长简单路径中的边数 。
示例 1：
输入：root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4] 输出：[2] 解释：上图展示了从树中移除以 4 为根节点的子树。 树的高度是 2（路径为 1 -> 3 -> 2）。
示例 2：
输入：root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8] 输出：[3,2,3,2] 解释：执行下述查询： - 移除以 3 为根节点的子树。树的高度变为 3（路径为 5 -> 8 -> 2 -> 4）。 - 移除以 2 为根节点的子树。树的高度变为 2（路径为 5 -> 8 -> 1）。 - 移除以 4 为根节点的子树。树的高度变为 3（路径为 5 -> 8 -> 2 -> 6）。 - 移除以 8 为根节点的子树。树的高度变为 2（路径为 5 -> 9 -> 3）。
提示：
- 树中节点的数目是
n 2 <= n <= 1051 <= Node.val <= n- 树中的所有值 互不相同
m == queries.length1 <= m <= min(n, 104)1 <= queries[i] <= nqueries[i] != root.val
解题思路
方法一：两次 DFS
我们先通过一次 DFS 遍历的深度，存放在哈希表 中，其中 表示节点 的深度。
然后我们设计一个函数 ，其中：
root表示当前节点；depth表示当前节点的深度；rest表示删除当前节点后，树的高度。
函数的计算逻辑如下：
如果节点为空，直接返回。否则，我们将 depth 加 ，然后将 rest 保存在 res 中。
接着递归遍历左右子树。
递归左子树前，我们计算从根节点到当前节点右子树最深节点的就，即 ，然后将其与 rest 比较，取较大值作为左子树的 rest。
递归右子树前，我们计算从根节点到当前节点左子树最深节点的就，即 ，然后将其与 rest 比较，取较大值作为右子树的 rest。
最后返回每个查询节点对应的结果值即可。
时间复杂度 ，空间复杂度 。其中 和 分别是树的节点数和查询数。
# 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 treeQueries(self, root: Optional[TreeNode], queries: List[int]) -> List[int]:
def f(root):
if root is None:
return 0
l, r = f(root.left), f(root.right)
d[root] = 1 + max(l, r)
return d[root]
def dfs(root, depth, rest):
if root is None:
return
depth += 1
res[root.val] = rest
dfs(root.left, depth, max(rest, depth + d[root.right]))
dfs(root.right, depth, max(rest, depth + d[root.left]))
d = defaultdict(int)
f(root)
res = [0] * (len(d) + 1)
dfs(root, -1, 0)
return [res[v] for v in queries]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n + q) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Candidate considers preprocessing depths and heights to avoid repeated computation per query.
- question_mark
Candidate identifies that tracking two maximum heights per level allows O(1) query resolution.
- question_mark
Candidate correctly handles edge cases such as removing nodes at maximum depth affecting tree height.
常见陷阱
外企场景- error
Recomputing tree height from scratch for each query, causing TLE for large n.
- error
Failing to account for the second largest height at a depth, returning wrong height when the largest node is removed.
- error
Incorrectly assuming subtree removal affects parent levels without adjusting maximums properly.
进阶变体
外企场景- arrow_right_alt
Compute remaining subtree sizes instead of heights after removal queries.
- arrow_right_alt
Answer subtree sum queries after removals using a similar traversal and precomputation.
- arrow_right_alt
Handle dynamic insertion and deletion with height updates using segment tree analogs.