今日题目
T538 把二叉搜索树转换为累加树(简单，二叉树遍历)
题目描述
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 原始二叉搜索树:5/ \2 13输出: 转换为累加树:18/ \20 13
标签
二叉树
解析
二叉搜索树的中序遍历，遍历的顺序是值从小到大。将这个顺序倒转，我们就可以得到从大到小的遍历顺序。利用全局变量表示遍历到某个节点时，大于这个节点的节点值之和，就可以实现累加的效果。
python解法
#利用函数传值的暴力解法
class Solution:def convertBST(self, root: TreeNode) -> TreeNode:def calc(root, value):if not root:return 0rightVal = calc(root.right, value)leftVal = calc(root.left, value + root.val + rightVal)rootVal = root.valroot.val += rightValreturn rootVal + leftVal + rightValcalc(root, 0)return root
#逆向中序遍历
class Solution:def convertBST(self, root: TreeNode) -> TreeNode:sum = 0def reversedInorderReversal(root):nonlocal sumif not root:returnreversedInorderReversal(root.right)sum += root.valroot.val = sumreversedInorderReversal(root.left)reversedInorderReversal(root)return root