Simple o(n) without map/set


  • 0
    D

    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;
    }
    };


  • 0
    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;
        }
    }

Log in to reply
 

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