My recursion solution,using map to optimize running time


  • 0
    N

    I save inorder position in a map,instead of searching every time.
    I have reduce running time.

    first solution takes 196 ms.
    second takes 116 ms.

    class Solution {
    public:
        vector<int> pre;
        vector<int> in;
        TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
            if(preorder.empty()||inorder.empty())return NULL;
            pre = preorder;
            in = inorder;
            TreeNode *res  = buildTree(0,0,inorder.size()-1);
            return res;
        }
        //prepos is position in preorder, inst is start position in inorder,inend is end in inorder
        TreeNode *buildTree(int prepos,int inst,int inend){
            if(inst>inend)return NULL;
            TreeNode *res = new TreeNode(pre[prepos]);
            int inpos = inst;
            for(int i=inst;i<=inend;i++)//searching every time
                if(in[i]==pre[prepos]){
                    inpos=i;
                    break;
                }
            res->left = buildTree(prepos+1,inst,inpos-1);
            res->right = buildTree(prepos+(inpos-inst)+1,inpos+1,inend);
            return res;
        }
        
    };
    

    second takes 116 ms.

    class Solution {
    public:
        vector<int> pre;
        vector<int> in;
        map<int,int> inorderPos; 
        TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
            if(preorder.empty()||inorder.empty())return NULL;
            for(int i=0;i<inorder.size();i++)
                inorderPos[inorder[i]]=i;
            pre = preorder;
            in = inorder;
            TreeNode *res  = buildTree(0,0,inorder.size()-1);
            return res;
        }
        
        TreeNode *buildTree(int prepos,int inst,int inend){
            if(inst>inend)return NULL;
            TreeNode *res = new TreeNode(pre[prepos]);
            int inpos = inorderPos[pre[prepos]];
            res->left = buildTree(prepos+1,inst,inpos-1);
            res->right = buildTree(prepos+(inpos-inst)+1,inpos+1,inend);
            return res;
        }
        
    };

  • 0
    C

    Hello there~
    I think my algorithm is the same as yours.But i got an TLE when i use java to write the code.

    public class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if(preorder.length == 0)
                return null;
            Map<Integer , Integer> map = new HashMap<Integer, Integer>();
            for(int i = 0 ; i < inorder.length ; i++){
                map.put(inorder[i],i);
            }
            return build(inorder,preorder,map,0,0,inorder.length-1);
        }
    
        public TreeNode build(int[] inorder , int[] preorder , Map<Integer , Integer> map ,int pos ,int start , int end ){
            if(pos >= preorder.length)
                return null;
            int rootVal = preorder[pos];
            if(end == start){
                TreeNode root = new TreeNode(rootVal);
                return root;
            }
            int inPos = map.get(rootVal);
            TreeNode root = new TreeNode(rootVal);
            root.left = build(inorder , preorder , map , pos+1 , start , inPos-1);
            root.right = build(inorder , preorder , map , pos+(inPos-start)+1 , inPos+1 , end);
            return root;
        }
    }

Log in to reply
 

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