移除子树后的二叉树高度
难度:
标签:
题目描述
给你一棵 二叉树 的根节点 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
代码结果
运行时间: 369 ms, 内存: 52.2 MB
/*
* 思路：
* 1. 使用流式操作处理树的高度计算和子树移除。
* 2. 构建辅助方法用于计算树的高度。
* 3. 使用流处理每个查询，移除子树并计算高度。
*/
import java.util.*;
import java.util.stream.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int[] treeQueries(TreeNode root, int[] queries) {
return Arrays.stream(queries)
.map(query -> {
TreeNode removedSubtree = removeSubtree(root, query);
int height = getHeight(root);
restoreSubtree(root, removedSubtree, query);
return height;
}).toArray();
}
private TreeNode removeSubtree(TreeNode root, int value) {
if (root == null) return null;
if (root.left != null && root.left.val == value) {
TreeNode removed = root.left;
root.left = null;
return removed;
}
if (root.right != null && root.right.val == value) {
TreeNode removed = root.right;
root.right = null;
return removed;
}
TreeNode left = removeSubtree(root.left, value);
if (left != null) return left;
return removeSubtree(root.right, value);
}
private void restoreSubtree(TreeNode root, TreeNode subtree, int value) {
if (root == null) return;
if (root.left == null && root.val != value) {
root.left = subtree;
return;
}
if (root.right == null && root.val != value) {
root.right = subtree;
return;
}
restoreSubtree(root.left, subtree, value);
restoreSubtree(root.right, subtree, value);
}
private int getHeight(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
}
解释
方法:
题解中首先定义了一个辅助函数 calDepth 来计算每个节点的深度，并存储在节点属性 depth 中。这个函数递归地计算左右子树的深度，然后返回当前节点的深度，即左右子树深度的最大值加一。在 treeQueries 函数中，使用栈来进行深度优先搜索 (DFS)，计算每个节点作为树根时树的最大深度。这种方法通过两次遍历，第一次确定每个节点的深度，第二次使用深度优先搜索的迭代方式来计算每个节点的高度。最终，对于每个查询返回删除该节点后树的高度。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在`calDepth`方法中，如果一个节点的左或右子树不存在，为什么将深度设为-1而不是0？这种设定对计算总体深度有什么影响？
▷🦆
题解中提到每次查询后树回到初始状态，但在代码实现中是如何保证树的状态在每个查询之后重置的？
▷🦆
在`treeQueries`函数中，两次DFS遍历看似相似，请问这两次遍历的目的分别是什么？为什么需要进行两次遍历？
▷🦆
在使用栈进行DFS时，栈中元素的第二个参数h代表什么？它如何帮助计算节点作为根时树的高度？
▷