My O(n)(19ms) solution without recusion. Hope help you!


  • 23
    P
    class Solution {
    public:
        TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
            TreeNode *root=NULL; stack<TreeNode *> MyData;
            if(preorder.empty()) return root;
            root = new TreeNode(preorder[0]);
            MyData.push(root); int index = 0;
           	for(int i=1; i<=preorder.size(); i++) {
           		TreeNode *cur = MyData.top();
           		if((MyData.top()->val)!=inorder[index]) {
           			cur->left = new TreeNode(preorder[i]);
           			MyData.push(cur->left);
           		} else {
           			while(!MyData.empty() && ((MyData.top()->val)==inorder[index])) {
           				cur=MyData.top(); MyData.pop(); index++; 
           			}
           			if(index<inorder.size()) {
           				cur->right = new TreeNode(preorder[i]);
           				MyData.push(cur->right);
           			} 
           		}  
           	}
           	return root;
        }
    };

  • 0
    S

    It's a great help! I transformed it into python and works fine. Thanks a lot!

    class Solution:
        # @param preorder, a list of integers
        # @param inorder, a list of integers
        # @return a tree node
        def buildTree(self, preorder, inorder):
            stack=[]
            root=TreeNode(0)
            if len(preorder)==0:
                return None
            root=TreeNode(preorder[0])
            stack.append(root)
            index=0
            for i in range(1,len(preorder)+1):
                cur=stack[-1]
                if(stack[-1].val!=inorder[index]):
                    cur.left=TreeNode(preorder[i])
                    stack.append(cur.left)
                else:
                    while(len(stack)!=0 and stack[-1].val==inorder[index]):
                        cur=stack[-1]
                        stack.pop()
                        index+=1
                    if(index<len(inorder)):
                        cur.right=TreeNode(preorder[i])
                        stack.append(cur.right)
                i+=1
            return root

  • 0
    R

    Cool. I also translate this into python, and it is faster than my own recursive or stack-based algorithm.

    My question is, how to come up with such a solution in the first place?


  • 0

    In the loop, I think the restriction i <= preorder.size() can also be written as i < preorder.size(), since the last node has already been identified when i equals preorder.size()-1.


  • 0
    E

    Really neat solution!! But I think

    if(index<inorder.size()) {
    

    is not needed?


  • 0
    M

    Hi,Prokias . I like your solution very much, the code seems simple but I can not totally get the idea. Can you explain it a little??
    Or anybody who can help : )


  • 0
    A

    @erica76 the code "if(index<inorder.size()) {" is needed,otherwise if "i" and "index" both equal to preorder.size() ,the last TreeNode wiil get an extra right son.for example,if the preorder is [1,2,3],the inorder is [2,1,3],the procedure is as follows:

    s.push(1)

    i=1
    1->left=2,s.push(2)

    i=2
    index=1,s.pop(2)
    index=2,s.pop(1)
    1->right=3,s.push(3)

    i=3
    index=3,s.pop(3)
    3->right=0,s.push(0)(maybe 0 or other value)

    return root


  • 0
    P

    @AmoCat
    The check for

           			if(index<inorder.size())
    

    is not needed, at least for the test cases that exist so far.

    In your example, there are 3 elements so the loop stops at index i==2. There should be no i==3 action.


  • 0
    P

    @michaelbit @ray8
    Stepping through it is the best way to get a handle on it but I'll give it a shot.

    By definition, preorder starts with the root and inorder starts with the left-most.

    So if a preorder value does not match the inorder value (which is initialized at index 0), then the value must be to the left. Not only to the left, but immediate left because the preorder traversal self->left... is immediately followed by self again.

    Pushing the values onto a stack allows tracking of the node creations. We've already taken care of all left node creations above. When do we create a right node? Popping from the stack traverses the inorder array (seen from an example) until the parent of the right node is popped. So we create the right node then and push it on the stack.


  • 0
    R

    This is not O(n)


Log in to reply
 

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