今日题目

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 0
            rightVal = calc(root.right, value)
            leftVal = calc(root.left, value + root.val + rightVal)
            rootVal = root.val
            root.val += rightVal
            return rootVal + leftVal + rightVal

        calc(root, 0)
        return root

#逆向中序遍历
class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        sum = 0

        def reversedInorderReversal(root):
            nonlocal sum
            if not root:
                return
            reversedInorderReversal(root.right)
            sum += root.val
            root.val = sum
            reversedInorderReversal(root.left)

        reversedInorderReversal(root)
        return root