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 } -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.248.137.47 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729958515.A.A61.html