把二叉搜索树转换为累加树

it2025-05-27  7

给定一个二叉搜索树(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/

最新回复(0)