給定一個二叉搜索樹（Binary Search Tree），把它轉換成為累加樹（Greater Tree)，使得每個節(jié)點的值是原來的節(jié)點值加上所有大于它的節(jié)點值之和。

例如：

輸入:?二叉搜索樹:
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 }

二叉搜索樹的中序遍歷時單調遞增的，他的反向遍歷就是單調遞減的。累加是只累加比他大的值，則從最大數的開始遍歷，這樣剛好對應的值就是當前的值加上前一個節(jié)點的值。

?

參考地址：https://leetcode-cn.com/problems/convert-bst-to-greater-tree/solution/ba-er-cha-sou-suo-shu-zhuan-huan-wei-lei-jia-sh-14/

總結

以上是生活随笔為你收集整理的把二叉搜索树转换为累加树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。