2641. Cousins in Binary Tree II
給一個二元樹的root
把這棵樹的所有node的value換成sum of all its cousins' values
cousin就是在同一個depth，但是parent root不同的nodes
思路:
先用bfs記錄每一個depth的sum
接著用depth
看這個node有沒有左、右子節點
有的話就把子節點那個depth的sum扣掉該node子節點的value然後傳下去
這樣就可以得到答案了
golang code：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func replaceValueInTree(root *TreeNode) *TreeNode {
queue := []*TreeNode{root}
rec := []int{}
for len(queue) > 0 {
cnt := len(queue)
sum := 0
for cnt > 0 {
node := queue[0]
queue = queue[1:]
sum += node.Val
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
cnt--
}
rec = append(rec, sum)
}
dfs(rec, 0, root, root.Val)
return root
}
func dfs(rec []int, level int, node *TreeNode, value int) {
if node == nil {
return
}
node.Val = rec[level] - value
child_value := 0
if node.Left != nil {
child_value += node.Left.Val
}
if node.Right != nil {
child_value += node.Right.Val
}
dfs(rec, level+1, node.Left, child_value)
dfs(rec, level+1, node.Right, child_value)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.63 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729696078.A.376.html