推 zenice: 怎麼連你也在力扣了== 10/23 16:36
推 zenice: 還我VT豚CP3 10/23 16:36
→ CP3isgood: 現在很閒就比較常刷了 10/23 16:39
推 sustainer123: 你版剩我不會寫程式了 10/23 16:41
→ sixB: 我好崇拜你 10/23 16:51
2641. Cousins in Binary Tree II
思路:
用兩次DFS
第一次先記錄每層sum
第二次更新每個node的val
func replaceValueInTree(root *TreeNode) *TreeNode {
var DFS1, DFS2 func(root *TreeNode, level int, levelSum map[int]int)
DFS1 = func(root *TreeNode, level int, levelSum map[int]int) {
levelSum[level] += root.Val
if root.Right != nil {
DFS1(root.Right, level+1, levelSum)
}
if root.Left != nil {
DFS1(root.Left, level+1, levelSum)
}
}
DFS2 = func(root *TreeNode, level int, levelSum map[int]int) {
if level == len(levelSum)-1 {
return
}
if level == 0 {
root.Val = 0
}
if root.Left != nil && root.Right != nil {
root.Left.Val, root.Right.Val = levelSum[level+1]-root.Left.Val-root.Right.Val, levelSum[level+1]-root.Right.Val-root.Left.Val
DFS2(root.Left, level+1, levelSum)
DFS2(root.Right, level+1, levelSum)
} else if root.Left != nil {
root.Left.Val = levelSum[level+1] - root.Left.Val
DFS2(root.Left, level+1, levelSum)
} else if root.Right != nil {
root.Right.Val = levelSum[level+1] - root.Right.Val
DFS2(root.Right, level+1, levelSum)
}
}
levelSum := map[int]int{}
DFS1(root, 0, levelSum)
DFS2(root, 0, levelSum)
return root
}
=====
今天開始紀錄
希望可以不要偷懶
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.184.173 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729672406.A.BD3.html