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
}
=====
今天開始紀錄
希望可以不要偷懶