20ms c++ recursive


  • 0
    D
    class Solution {
    private: 
        unordered_map<int,int> inmap;
    public:
        TreeNode* dfs(vector<int>& inorder, int ileft, int iright, vector<int>& preorder, int pleft, int pright)
        {
             if(ileft > iright) return NULL;
             int value = preorder[pleft];
             int iroot = inmap[value];
        
             TreeNode* root = new TreeNode(value);
             if (ileft == iright) return root;
        
             int len = iroot - ileft;
        
             root->left = dfs(inorder, ileft, iroot-1, preorder, pleft + 1, pleft + len);
             root->right= dfs(inorder, iroot+1, iright, preorder, pleft+len+1, pright);
             return root;    
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
             int n = inorder.size();
             int m = preorder.size();
        
             for(int i = 0; i < n;i++)
                  inmap[inorder[i]] = i;
             return dfs(inorder, 0, n-1, preorder, 0, m-1);   
         }
    };

  • 0
    S

    @duoduo Don't you think there will same number of elements in different types of traversal of a tree ? Nice code btw !


Log in to reply
 

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