1038. Binary Search Tree to Greater Sum Tree
給一顆二元樹
把所有節點的值加上比他還小節點
然後回傳
思路:
沒什麼難的
就從柚子樹開始DFS下去
用一個變數記錄到目前為止的總和
這樣就好
golang code :
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func bstToGst(root *TreeNode) *TreeNode {
var sum int
dfs(root,&sum)
return root
}
func dfs(node *TreeNode,sum *int){
if node==nil{
return
}
dfs(node.Right,sum)
tmp:=(*sum)
(*sum)+=node.Val
node.Val+=tmp
dfs(node.Left,sum)
}