Simple C++ dfs solution


  • 1
    class Solution {
    private: 
        unordered_map<int, int> inm;
        
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            int n = preorder.size(), i = 0;
            for(auto v: inorder) inm[v] = i++;
            
            return dfs(preorder, 0, n - 1, inorder, 0, n - 1);
        }
        
        TreeNode* dfs(vector<int>& preorder, int pleft, int pright, vector<int>& inorder, int ileft, int iright){
            if(pleft > pright) return nullptr;
            int val = preorder[pleft];
            TreeNode* root = new TreeNode(val);
            if(pleft == pright) return root;
            
            int iroot = inm[val], nleft = iroot - ileft;
            root->left = dfs(preorder, pleft + 1, pleft + nleft, inorder, ileft, iroot - 1);
            root->right = dfs(preorder, pleft + nleft + 1, pright, inorder, iroot + 1, iright);
            
            return root;
        }
    };

Log in to reply
 

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