C++ O(n) DFS solution beath 91% submissions


  • 10

    Example

           13
         /    \
        2      3
       / \    /
      5   6  7
            / \
           8   9
                \
                10
                /
              12
    
    5,  2,  6,  13,  8,  7,  9,  12,  10,  3
    ---left--- root  ---------right---------
    
    5,  6,  2,  8,  12,  10,  9,  7,  3,  13
    ---left---	---------right---------- root 
    

    Code

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

  • 0
    A

    @Ximin.Z
    Actually, we don't need to pass the iright and pleft, which would make the function signature more concise.


  • 0
    S

    @Ximin.Z what we happen if tree contain duplicate elements ??


Log in to reply
 

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