题目描述
- 给定一棵BST,给每个节点都加上大于自身数值的节点的值
示例
输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
输入:root = [0,null,1]
输出:[1,null,1]
解释:0 1\ => \1 1
题解
- 思路:dfs
- 右 -> 根 -> 左,边遍历边累加
- 跟 cpp 不同,sum 不能设置成全局变量,需要套一个函数保存 sum,且 sum 不能用值传递
func bstToGst(root *TreeNode) *TreeNode {sum := 0dfs(root, &sum)return root
}func dfs(p *TreeNode, sum *int) {if p == nil { return }dfs(p.Right, sum)t := p.Valp.Val += *sum*sum += tdfs(p.Left, sum)
}