Invert the BST twice, unnecessary steps, but easy to understand


  • 0
    F
            head = root
            mem = 0
            s = []
            while s or root:
                if s:
                    root = s.pop()
                root.left, root.right = root.right, root.left
                if root.left:
                    s.append(root.left)
                if root.right:
                    s.append(root.right)
                root = None
            s = []
            root = head
            while s or root:
                while root:
                    s.append(root)
                    root = root.left
                root = s.pop()
                root.val += mem
                mem = root.val
                root = root.right
            s = []
            root = head
            while s or root:
                if s:
                    root = s.pop()
                root.left, root.right = root.right, root.left
                if root.left:
                    s.append(root.left)
                if root.right:
                    s.append(root.right)
                root = None
            return head
    

Log in to reply
 

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