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

?

例如：

輸入: 原始二叉搜索樹:5/ \2 13輸出: 轉換為累加樹:18/ \20 13

?

注意：本題和 1038:?https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

DFS

先拿到整個二叉樹所有的節點值放到列表里，然后DFS直接加和。

Code

def convertBST(self, root: TreeNode) -> TreeNode:def getValues(node: TreeNode):nonlocal valuesif node:values.append(node.val)getValues(node.left)getValues(node.right)def dfs(node: TreeNode):if node:node.val += sum(values[values.index(node.val) + 1:])dfs(node.left)dfs(node.right)values = []getValues(root)values.sort()dfs(root)return root

寫博客的時候才發現題目說的是二叉搜索樹，直接把當前節點值累加右子樹節點值就可以了，草率了。

總結

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

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