子树删除查询后二叉树的高度

2458。子树删除查询后二叉树的高度

难度：难

主题：数组、树、深度优先搜索、广度优先搜索、二叉树

给定一个具有 n 个节点的 二叉树 的根。每个节点都被分配一个从 1 到 n 的唯一值。您还会获得一个大小为 m 的数组查询。

您必须在树上执行 m 独立 查询，其中在第 i^th 查询中执行以下操作：

• 从树中删除以值为queries[i]的节点为根的子树。 保证查询[i]将不等于根的值。

返回大小为m的数组答案，其中answer[i]是执行第i^第查询后树的高度。

注意：

• 查询是独立的，因此树在每次查询后都会返回到其初始状态。
• 树的高度是从根到树中某个节点的最长简单路径的边数。

示例1：

• 输入： root = [1,3,4,2,null,6,5,null,null,null,null,null,7]，查询 = [4]
• 输出： [2]
• 说明： 上图显示了删除以值为 4 的节点为根的子树后的树。
  • 树的高度为 2（路径 1 -> 3 -> 2）。

示例2：

• 输入： root = [5,8,9,2,1,3,7,4,6​​]，查询 = [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 5
• 1
• 树中的所有值都是唯一。
• m == requests.length
• 1 4)
• 1
• 查询[i] != root.val

提示：

1. 尝试预先计算从 1 到 n 的每个节点的答案，并在 O(1) 内回答每个查询。
2. 计算每个子树的高度后，可以在单次树遍历中预先计算答案。

解决方案：

该解决方案采用了两遍方法：

1. 计算树中每个节点的高度。
2. 删除以每个查询节点为根的子树后，确定树的最大高度。

让我们用 PHP 实现这个解决方案：2458。子树删除查询后二叉树的高度

代码分解

1。类定义和属性：

class Solution {

    private $valToMaxHeight = [];
    private $valToHeight = [];

• valToMaxHeight：该数组将存储删除每个节点的子树后树的最大高度。
• valToHeight：该数组将存储每个节点子树的高度。

2。主要功能：

function treeQueries($root, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• 函数treeQueries获取树的根和查询数组。
• 它首先调用 height 函数来计算每个节点的高度。
• 然后，它调用 dfs（深度优先搜索）函数来计算子树删除后的最大高度。
• 最后，它用每个查询的结果填充答案数组。

3。高度计算：

private function height($node) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• 该函数递归计算每个节点的高度。
• 如果节点为空，则返回0。
• 如果节点的高度已经计算出来，它会从缓存中检索它（valToHeight）。
• 根据左右子节点的高度计算高度，并将其存储在 valToHeight 中。

4。深度优先搜索最大高度：

private function dfs($node, $depth, $maxHeight) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

• 此函数执行 DFS 来计算删除每个节点的子树后树的最大高度。
• 它在 valToMaxHeight 中记录当前节点的当前最大高度。
• 它计算左右子树的高度并相应地更新最大高度。
• 它递归地调用自己的左右子节点，更新深度和最大高度。

示例演练

让我们逐步看一下示例。

输入示例：

// Tree Structure
//        1
//       / \
//      3   4
//     /   / \
//    2   6   5
//         \
//          7

$root = [1, 3, 4, 2, null, 6, 5, null, null, null, null, null, 7];
$queries = [4];

初始高度计算：

• 树根的高度为1:3
• 树根的高度为3：2
• 以 4:2 为根的树的高度（以 6 和 5 为根的子树的高度）
• 以 6:1 为根的树的高度（仅节点 7）
• 以2:0为根的树的高度（叶节点）

高度计算后，valToHeight 将如下所示：

class Solution {

    private $valToMaxHeight = [];
    private $valToHeight = [];

最大高度的 DFS：

• 对于根 (1)，删除子树 4 个叶子：
  • 左高度：2（以 3 为根）
  • 右高：1（以 5 为根）
• 因此，去掉 4 后的最大高度为 2。

查询后结果数组：

• 对于查询 4，结果将是 [2]。

最终输出

所提供输入的结果将是：

function treeQueries($root, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

这种结构化方法确保我们在初始预处理后有效地计算必要的高度并在恒定时间内回答每个查询。整体复杂度为 O(n m)，其中 n 是树中的节点数， m 是查询次数。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是子树删除查询后二叉树的高度的详细内容。更多信息请关注PHP中文网其他相关文章！