17line 75ms non recursive python code.


  • 0
    Y
    # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        # @param inorder, a list of integers
        # @param postorder, a list of integers
        # @return a tree node
        def buildTree(self, inorder, postorder):
            if not inorder:
                return None
            inordermap={inorder[i]:i for i in range(len(inorder))}
            dummy=TreeNode(0)
            stack=[(0,len(inorder)-1,0,len(postorder)-1,dummy,True)]
            while stack:
                instart,inend,pstart,pend,root,isLeft=stack.pop()
                if pend>=pstart:
                    child=TreeNode(postorder[pend])
                    if isLeft:
                        root.left=child
                    else:
                        root.right=child
                    temp=inordermap[postorder[pend]]
                    stack.append((temp+1,inend,pstart+temp-instart,pend-1,child,False))
                    stack.append((instart,temp-1,pstart,pstart-1+temp-instart,child,True))
            return dummy.left

Log in to reply
 

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