O(n^2) solution submitted but when I use a map to do it in O(n), it times out on the last case.


  • 0
    N
    TreeNode* buildTree_util(vector<int>& preorder, int &start, vector<int>& inorder, int left, int right, unordered_map<int, int> hash_map)
        {
            if (left > right)
                return NULL;
            TreeNode *root = new TreeNode(0);
            int node = preorder[start++];
            root->val = node;
            /*
            int i = left;
            for (; i < right; i++)
            {
                if (inorder[i] == node)
                    break;
            }
            */
            int i;
            if (left == right)
                i = left;
            else
                i = hash_map[node];
            root->left = buildTree_util(preorder, start, inorder, left, i - 1, hash_map);
            root->right = buildTree_util(preorder, start, inorder, i + 1, right, hash_map);
            return root;
            
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            int start = 0;
            unordered_map<int, int> hash_map;
            int count = 0;
            for (int num: inorder)
                hash_map[num] = count++;
            return buildTree_util(preorder, start, inorder, 0, inorder.size() - 1, hash_map);
        }
    

Log in to reply
 

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