Share my solution with hashmap, beat 90%


  • 0
    O
    class Solution {
    public:
    	TreeNode* builder(vector<int>& preorder, vector<int>& inorder,
    					  int pStart, int pEnd, int iStart, int iEnd,
    					  unordered_map<int, int>& indicesMap) {
    		if (pStart > pEnd || iStart > iEnd)
    			return nullptr;
    		TreeNode* root = new TreeNode(preorder[pStart]);
    		int rootIndex = indicesMap[root->val];
    		int leftLen = rootIndex - iStart, rightLen = iEnd - rootIndex;
    		root->left = builder(preorder, inorder, 
    							 pStart + 1, pStart + leftLen, iStart, rootIndex - 1, 
    							 indicesMap);
    		root->right = builder(preorder, inorder, 
    							  pEnd - rightLen + 1, pEnd, rootIndex + 1, iEnd, 
    							  indicesMap);
    		return root;
    	}
    	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    		unordered_map<int, int> indicesMap;
    		for (int i = 0; i < inorder.size(); i++)
    			indicesMap[inorder[i]] = i;
    		return builder(preorder, inorder, 
    					   0, preorder.size() - 1, 0, inorder.size() - 1, 
    					   indicesMap);
    	}
    };

Log in to reply
 

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