20ms c++ recursion solution


  • 1
    T

    Use a hash map to speed up the linear search of the index of root in "inorder", which, in the worst case, may take O(n^2) time.

       class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            if(preorder.size() == 0)
                return nullptr;
            unordered_map<int, int> inorder_map;
            for(size_t i = 0; i < inorder.size(); ++i) {
                inorder_map[inorder[i]] = i;
            }
            return buildTreeHelper(preorder, inorder, inorder_map, 0, preorder.size(), 0, inorder.size());
        }
        
        TreeNode* buildTreeHelper(vector<int>& preorder, vector<int>& inorder, unordered_map<int, int>& inorder_map,
                                  size_t pstart, size_t pend, size_t istart, size_t iend) {
            if(pend == pstart) {
                return nullptr;
            }
            
            size_t i = inorder_map[preorder[pstart]];
    
            TreeNode* node = new TreeNode(preorder[pstart]);
            node->left = buildTreeHelper(preorder, inorder, inorder_map,
                                         pstart + 1, pstart + 1 + i - istart, istart, i);
            node->right = buildTreeHelper(preorder, inorder, inorder_map,
                                          pstart + 1 + i - istart, pend, i + 1, iend);
            return node;
            
        }
    };

Log in to reply
 

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