Python, No recursion, Stack Iteration Solution


  • 0

    Just do a Reverse-Post-Order Traversal and add value during traversing. Record the previous node value.

    class Solution(object):
        def convertBST(self, root):
            if not root:
                return root
            prev = 0
            stack = [(False, root)]
            while stack:
                visited, node = stack.pop()
                if visited:
                    node.val += prev
                    prev = node.val
                else:
                    if node.left:
                        stack.append((False, node.left))
                    stack.append((True, node))
                    if node.right:
                        stack.append((False, node.right))
            return root

Log in to reply
 

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