2458. Height of Binary Tree After Subtree Removal Queries
思路:
HARD好难，看别人的想法
做两次DFS
先由左至右遍历取得移除左子树后的最大高度
再由右至左遍历取得移除右子树后的最大高度
就可以得到每个点移除后的最大高度
最后遍历queries就可以得到答案
func treeQueries(root *TreeNode, queries []int) []int {
item := &Item{maxHeightAfterRemove: map[int]int{}}
item.L2R(root, 0)
item.maxHeight = 0
item.R2L(root, 0)
ans := make([]int, len(queries))
for i, query := range queries {
ans[i] = item.maxHeightAfterRemove[query]
}
return ans
}
func (item *Item) L2R(node *TreeNode, height int) {
if node == nil {
return
}
item.maxHeightAfterRemove[node.Val] = item.maxHeight
item.maxHeight = max(item.maxHeight, height)
item.L2R(node.Left, height + 1)
item.L2R(node.Right, height + 1)
}
func (item *Item) R2L(node *TreeNode, height int) {
if node == nil {
return
}
item.maxHeightAfterRemove[node.Val] = max(item.maxHeightAfterRemove[node.Val], item.maxHeight)
item.maxHeight = max(item.maxHeight, height)
item.R2L(node.Right, height + 1)
item.R2L(node.Left, height + 1)
}
type Item struct {
maxHeightAfterRemove map[int]int
maxHeight int
}