Re: [閒聊] 每日leetcode
看板Marginalman作者CP3isgood (夜空メル的かぷ民)時間1年前 (2024/10/27 00:01)推噓1(1推 0噓 0→)留言1則, 1人參與討論串1052/1554 (看更多)
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
推
10/27 00:23,
1年前
, 1F
10/27 00:23, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1052 之 1554 篇)：