Python one-pass In-order traversal solution


  • 0
    G

    Instead of visiting each node in-order(smallest to greatest), do the reverse.

    class Solution(object):
        sum = 0 
        def reverse_order(self,node):
            if node: 
                self.reverse_order(node.right)
                node.val += self.sum
                self.sum = node.val
                self.reverse_order(node.left)
        
        def convertBST(self, root):
            """
            :type root: TreeNode
            :rtype: TreeNode
            """
            self.reverse_order(root)
            return root
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.