给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如:
输入: 二叉搜索树: 5 / \ 2 13输出: 转换为累加树: 18 / \ 20 13
反序中序遍历
func convertBST(root *TreeNode) *TreeNode {
sum := 0
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node != nil {
dfs(node.Right)
sum += node.Val
node.Val = sum
dfs(node.Left)
}
}
dfs(root)
return root
}
二叉搜索树的中序遍历时单调递增的,他的反向遍历就是单调递减的。累加是只累加比他大的值,则从最大数的开始遍历,这样刚好对应的值就是当前的值加上前一个节点的值。
参考地址:https://leetcode-cn.com/problems/convert-bst-to-greater-tree/solution/ba-er-cha-sou-suo-shu-zhuan-huan-wei-lei-jia-sh-14/