c++ dfs solution


  • 0
    H
    class Solution {
    public:
        unordered_map<int, int> um; // map inorder[i] to i
        TreeNode* dfs(vector<int>& inorder, int ileft, int iright, vector<int>& postorder, int pleft, int pright) {
            if(ileft > iright || pleft > pright) return nullptr;
            int val = postorder[pright]; // last element in postorder is the root node
            TreeNode* root = new TreeNode(val);
            int root_idx = um[val]; // root index in inorder
            int nleft = root_idx - ileft; // size of left sub-tree
            root->left = dfs(inorder, ileft, root_idx-1, postorder, pleft, pleft + nleft - 1);
            root->right = dfs(inorder, root_idx+1, iright, postorder, pleft + nleft, pright - 1);
            return root;
        }
        
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            int n = inorder.size(), i = 0;
            for(int val : inorder) um[val] = i++;
            return dfs(inorder, 0, n-1, postorder, 0, n-1);
        }
    };
    

Log in to reply
 

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