题目

难度：★★☆☆☆
类型：二叉树

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

例如：

输入: 二叉搜索树:

              5
            /   \
           2     13

输出: 转换为累加树:

             18
            /   \
          20     13

在真实的面试中遇到过这道题？

解答

class Solution:
    
    def convertBST(self, root):
        al = [0]
        self.bianli(root, al)
        return root
    
    def bianli(self, root, addlist):
        if not root:
            return
        self.bianli(root.right, addlist)
        addlist.append(root.val)
        root.val += sum(addlist[:-1])
        self.bianli(root.left, addlist)

如有疑问或建议，欢迎评论区留言~