My Python O(1) extra space and O(n) time method--inorder traversal without recursive and Stack.


  • 0
    Z
    class Solution(object):
        def convertBST(self, root):
            """
            :type root: TreeNode
            :rtype: TreeNode
            """
            
            if root==None:
                return None
            lastNode=None
            cur=root
            
            while not cur==None:
                if cur.right==None:
                    if lastNode==None:
                        pass
                    else:
                        cur.val+=lastNode.val
                    lastNode=cur
                    cur=cur.left
                else:
                    p=cur.right
                    while not p.left==None and not p.left==cur:
                        p=p.left
                    if p.left==None:
                        p.left=cur
                        cur=cur.right
                    else:
                        p.left=None
                        if lastNode==None:
                            pass
                        else:
                            cur.val+=lastNode.val
                        lastNode=cur
                        cur=cur.left
            return root
    

Log in to reply
 

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