代码随想录 -- 二叉树 -- 把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

思路：

定义pre变量用来记录当前节点的前一个节点（右中左顺序遍历）的值。

递归出口：当root为空时，return。

单层递归逻辑：（右中左）

• 右：self.tra(root.right)
• 中：令root的值为它本身加上pre，更新pre为当前root的值；
• 左：self.tra(root.left)

class Solution(object):
    def tra(self,root):
        if root==None:
            return
        self.tra(root.right)
        root.val=root.val+self.pre
        self.pre=root.val
        self.tra(root.left)
    def convertBST(self, root):
        self.pre=0
        self.tra(root)
        return root

注意：

定义pre变量时，使用self来定义，即定义全局变量pre。