DEV Community
·
2458. 删除子树查询后的二叉树高度
💡
原文英文，约1100词，阅读约需4分钟。
📝
内容提要
给定一棵二叉树和查询数组，通过预计算每个节点的高度和删除子树后的最大高度，可以在O(1)时间内快速返回每次查询后的树高。整体复杂度为O(n + m)。
🎯
关键要点
- 给定一棵二叉树和查询数组，要求在O(1)时间内返回每次查询后的树高。
- 树的高度是从根到某个节点的最长简单路径的边数。
- 通过预计算每个节点的高度和删除子树后的最大高度，可以快速回答查询。
- 整体复杂度为O(n + m)，其中n是树的节点数，m是查询的数量。
- 使用两次遍历的方法：第一次计算每个节点的高度，第二次计算删除子树后的最大高度。
- 在每次查询后，树会恢复到初始状态，确保查询是独立的。
- 示例中展示了如何通过删除不同节点的子树来计算树的高度变化。
➡️
