O(n) c++ recursive solution - 23ms with comments


  • 8
    P
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
            unordered_map<int, int> inorder_map;
            // we need a map to look up the position of root in inorder, so
            // that we can divide the tree into separate subtrees,
            // reduces the complexity from n^2 to n assuming good hashing by unodered_map
            for (int i = 0; i < inorder.size(); ++i) {
                inorder_map[inorder[i]] = i;
            }
            return buildTreeHelper(postorder, 0, inorder.size()-1, 0, postorder.size()-1, inorder_map);
        }
        
        TreeNode* buildTreeHelper(vector<int>& post, int is, int ie, int ps, int pe, unordered_map<int, int>& inorder_map) {
            
            if (is > ie || ps > pe) {
                return NULL;
            }
            int root_val = post[pe];
            TreeNode* root = new TreeNode(root_val);
            int i = inorder_map.find(root_val)->second;
            // number of nodes in left subtree
            int l = i-is;
            root->left = buildTreeHelper(post, is, is+l-1, ps, ps+l-1, inorder_map);
            root->right = buildTreeHelper(post, is+l+1, ie, ps+l, pe-1, inorder_map);
            
            return root;
        }

  • 1
    L

    Hi pankit,

    Thanks for sharing your code.
    In your code, the start point is is+l-1/ps+l-1 for inorder/postorder. I do not quite understand why we should calculate by using (start point + len - 1) rather than (start point)? Becase l = i-is, is+l-1 = is+(i-is)-1 = i-1.

    I tried to modify your code but it seemed incorrect for invalid inorder/postorder pairs like [1,3,2] and [3,2,1]. Any reason for that?


Log in to reply
 

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