My C++ Solution


  • 12
    H
    class Solution {
    
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            
            return helper(inorder,0,inorder.size(),postorder,0,postorder.size());
        }
    private:
        TreeNode* helper(vector<int>& inorder,int i,int j,vector<int>& postorder,int ii,int jj)
        {
            // 每次取postorder的最后一个值mid,将其作为树的根节点
            // 然后从inroder中找到mid,将其分割成为两部分,左边作为mid的左子树,右边作为mid的右子树
            // tree:     8 4 10 3 6 9 11
            // Inorder   [3 4 6] 8 [9 10 11]
            // postorder [3 6 4]   [9 11 10] 8
    
            if(i >= j || ii >= jj)
                return NULL;
            
            int mid = postorder[jj - 1];
            
            auto f = find(inorder.begin() + i,inorder.begin() + j,mid);
            
            int dis = f - inorder.begin() - i;
            
            TreeNode* root = new TreeNode(mid);
            root -> left = helper(inorder,i,i + dis,postorder,ii,ii + dis);
            root -> right = helper(inorder,i + dis + 1,j,postorder,ii + dis,jj - 1);
            
            return root;
            
        }
    };

  • -1
    M

    Super clear solution!
    I suggest you can replace
    find(inorder.begin() + i,inorder.begin() + j,mid);
    to
    lower_bound(inorder.begin() + i,inorder.begin() + j,mid);
    since inOrder array is in order, can use binary search.


  • 0
    M

    Oh, sorry, it is not ture that inorder array is in order, forget about my suggestion.


  • 0
    G

    My solution is similar but only uses iterator f to do the math. The use of dis inspired me and I made my solution a lot more clear. Thanks!


  • 0
    M

    Why binary search is not working here?


  • 1

    It's not binary search tree.


Log in to reply
 

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