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;
}
};
My O(n)(19ms) solution without recusion. Hope help you!


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

@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

@AmoCat
The check forif(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.

@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 leftmost.
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.