My fast C++ solution using map


  • 0
    P
    
    class Solution {
    public:
         TreeNode* findOrder(vector<int> &preorder, int preorder_start, int preorder_end, vector<int> &inorder, 
                                                   int inorder_start, int inorder_end, unordered_map< int, int> &cache) {
                                                       
        if (inorder_start >= inorder_end || preorder_start >= preorder_end) return NULL;
        TreeNode* root = new TreeNode(preorder[preorder_start]);
        int rootInorderIndex = cache[root->val];
        int leftsize = rootInorderIndex - inorder_start;
    
        root->left = findOrder(preorder, preorder_start + 1, preorder_start + 1 + leftsize, inorder, inorder_start, rootInorderIndex, cache );
        root->right = findOrder(preorder, preorder_start + leftsize + 1, preorder_end, inorder, rootInorderIndex + 1, inorder_end, cache);
        return root;
      }
      
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            unordered_map< int, int> cache;
            int size = inorder.size();
            if (size == 0) return NULL;
            for(int i = 0; i < size; ++i) {
            	cache[inorder[i] ] = i; //number of nodes to its left
            }
            return findOrder(preorder, 0, preorder.size(), inorder, 0, inorder.size(), cache);
        }
    };
    

Log in to reply
 

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