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

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 二叉搜索树:
5
/ \
2 13
输出: 转换为累加树:
18
/ \
20 13

 反序中序遍历

func convertBST(root *TreeNode) *TreeNode {sum := 0var dfs func(*TreeNode)dfs = func(node *TreeNode) {if node != nil {dfs(node.Right)sum += node.Valnode.Val = sumdfs(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/

总结

以上是生活随笔为你收集整理的把二叉搜索树转换为累加树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。