Simple o(n) without map/set

• class Solution {
public:
int pos1,pos2;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int val = -1) {
if(pos1 >= preorder.size() || pos2 >= inorder.size())
return NULL;
TreeNode *T = new TreeNode(preorder[pos1]);
pos1 ++;
if(preorder[pos1 - 1] != inorder[pos2])
T->left = buildTree(preorder,inorder,T -> val);
pos2++;
if(pos2 != preorder.size() && inorder[pos2] != val)
T-> right = buildTree(preorder,inorder,val);
return T;
}
};

• Your solution is really good, too bad you lack some talent to format code.

Here's a translated and formatted Java version:

``````public class Solution {
int prePos, inPos;
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, inorder, -1);
}
public TreeNode buildTree(int[] preorder, int[] inorder, int val) {
if (prePos >= preorder.length || inPos >= inorder.length) return null;

TreeNode node = new TreeNode(preorder[prePos]);

prePos++;
if (preorder[prePos - 1] != inorder[inPos]) {
node.left  = buildTree(preorder, inorder, node.val);
}

inPos++;
if (inPos!= preorder.length && inorder[inPos] != val) {
node.right = buildTree(preorder, inorder, val);
}
return node;
}
}``````

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