Python simple recursive and iterative solution


  • 0
    X

    Recursive:

    def convertBST(self, root):
            def trav(root, s):
                if not root:
                    return 0
                r = trav(root.right, s)
                root.val += r + s
                l = trav(root.left, root.val)
                return root.val-s + l
            trav(root, 0)
            return root
    

    Iterative:

        def convertBST(self, root):
            r, stk, s = root,[], 0
            while stk or r:
                if r:
                    stk.append(r)
                    r = r.right
                else:
                    r = stk.pop()
                    r.val = s = r.val + s
                    r = r.left
            return root
    

Log in to reply
 

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