【Leetcode】538. Convert BST to Greater Tree 解题报告

给定一个BST,更新每个节点的值，更新的方式为当前节点的值+= 比它大的节点值的和

方法1 全局变量+递归

按照右子树-根节点-左节点的访问顺序，这样对于二叉排序树的访问就是按照从大到小来的，记录之前访问过的节点和并加到当前节点上即可

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        self.res = 0
        self.DFS(root)
        return root
    
    def DFS(self, root):
        if root == None:
            return 
        self.DFS(root.right)
        root.val += self.res
        self.res = root.val
        self.DFS(root.left)

方法2 非递归加全局变量

按照右-根-左的顺序非递归访问BST树，其实就是先序遍历倒过来写

class Solution2:
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        stack = []
        pNode =root
        sumer = 0
        while(pNode or len(stack)):
            if pNode:
                stack.append(pNode)
                pNode = pNode.right
            else:
                pNode = stack.pop()
                pNode.val += sumer
                sumer = pNode.val
                pNode = pNode.left
        return root

方法3 Morris 算法 倒先序遍历

class Solution3:
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        pNode = root
        res = 0
        while(pNode):
            if pNode.right == None:
                pNode.val += res
                res = pNode.val
                pNode = pNode.left
            else:
                tmp = pNode.right
                while(tmp.left and tmp.left != pNode):
                    tmp = tmp.left
                if tmp.left == None:
                    tmp.left = pNode
                    pNode = pNode.right
                else:
                    tmp.left = None
                    pNode.val += res
                    res = pNode.val
                    pNode = pNode.left
        return root