Recursive code, can it be better?


  • 0
    W
    class Solution {
    public:
        TreeNode *build(vector<int> &preorder, int lp, vector<int> &inorder, int li, int len) {
            if (len <= 0 || !(0<=lp&&lp<preorder.size()) || !(0<=li&&li<inorder.size())) return NULL;
            TreeNode *ret = new TreeNode(preorder[lp]);
            int idx = li;
            while (idx < li+len && inorder[idx] != ret->val) ++idx;
            ret->left = build(preorder, lp+1, inorder, li, idx-li);
            ret->right = build(preorder, lp+1+idx-li, inorder, idx+1, len-idx+li-1);
            return ret;
        }
        TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
            return build(preorder, 0, inorder, 0, preorder.size());
        }
    };

  • 2
    F

    Yes.

    You tried to find the position of a value in the in-order array:

    while (idx < li+len && inorder[idx] != ret->val) ++idx;
    

    This can be accelerated if you build a hash map at the beginning.

    This way, the overall running time is reduced from O(n^2) to expected O(n).


  • 0
    W

    nice idea!
    thanks


  • 0
    W

    can it be more clean?


  • 0
    F

    The boundary condition could be simplified to just len <= 0. Otherwise it looks clean enough to me.


Log in to reply
 

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