Sharing my straightforward recursive solution


  • 51
    Z
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        return create(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
    
    TreeNode* create(vector<int>& preorder, vector<int>& inorder, int ps, int pe, int is, int ie){
        if(ps > pe){
            return nullptr;
        }
        TreeNode* node = new TreeNode(preorder[ps]);
        int pos;
        for(int i = is; i <= ie; i++){
            if(inorder[i] == node->val){
                pos = i;
                break;
            }
        }
        node->left = create(preorder, inorder, ps + 1, ps + pos - is, is, pos - 1);
        node->right = create(preorder, inorder, pe - ie + pos + 1, pe, pos + 1, ie);
        return node;
    }
    

    The first element in preorder array can divide inorder array into two parts. Then we can divide preorder array into two parts. Make this element a node. And the left sub-tree of this node is the left part, right sub-tree of this node is the right part. This problem can be solved following this logic.


  • 0
    M

    Nice answer, thanks.


  • 0
    R

    c++ recursive solution (easy to understand)

    int findv(int a, vector<int> arr) {
            for(int i=0; i< arr.size(); i++)
                if(arr[i] == a)
                    return i;
        }
        TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
            TreeNode *root = 0;
            int id, N;
            vector<int> temp;
            if(! inorder.empty()) {
                N = inorder.size();
                root = new TreeNode(preorder[0]);
                id = findv(preorder[0], inorder);
                preorder.erase(preorder.begin());
                if(id!=0) {
                    temp = vector<int>(inorder.begin(), inorder.begin()+id);
                    root->left = buildTree(preorder, temp);
                }
                if(id< N-1) {
                    temp = vector<int>(inorder.begin()+id+1,inorder.begin()+ N);
                    root->right = buildTree(preorder, temp);
                }
            }
            return root;
        }

  • 0
    Z

    Very clear,thanks


  • 0
    R

    This one is nice. Thanks mate


  • 0
    M

    dat is so clear thx.


  • 0
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            return help(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
        }
        
        TreeNode* help(vector<int>& preorder, vector<int>& inorder, int pre_start, int pre_end, int in_start, int in_end) {
            int len=pre_end-pre_start+1;
            if(len<=0)  return NULL;
            if(len==1)  return new TreeNode(preorder[pre_start]);
            TreeNode* root = new TreeNode(preorder[pre_start]);
            int index;
            for(index=in_start; index<=in_end; index++){
                if(inorder[index]==preorder[pre_start])   break;
            }
            int left_len=index-in_start;
            int right_len=len-left_len-1;
            root->left = help(preorder, inorder, pre_start+1, pre_start+left_len, in_start, in_start+left_len-1);
            root->right = help(preorder, inorder, pre_end-right_len+1, pre_end, index+1, in_end);
            return root;
        }
    };

  • 1

    similar idea, the first element in the preorder is the root node. then find the element in the inorder equal the the root node, devide the inorder vector into two parts, the left part is the left child tree and the right part is the right child tree. and the preorder has equal number nodes in correspondin part

    class Solution {
    TreeNode*  findDown(vector<int> &preorder, int bp, int ep, vector<int>& inorder, int bi, int ei, TreeNode* root)
    {
        if(bp>ep || bi>ei) return root;
        
        root = new TreeNode(preorder[bp]);
        
        //find the match of preorder[bp]
        for(int i=bi; i<=ei; i++){
            if(inorder[i]==preorder[bp]){
                int num=i-bi;
                root->left=findDown(preorder, bp+1, bp+num, inorder, bi, i-1, root->left);
                root->right=findDown(preorder, bp+num+1, ep, inorder, i+1, ei, root->right);
            }
        }
        return root;
    }
    public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* head=0;
        if(!preorder.size()) return head;
        
        head=findDown(preorder,0,preorder.size()-1,inorder, 0, preorder.size()-1, head);
        return head;
        
    }
    

    };


  • 0
    L

    Very short cpp solution without helper function.

        TreeNode* buildTree(vector<int> preorder, vector<int> inorder) {
            if(inorder.empty()||preorder.empty()) return NULL;
            int i=-1;
            while(preorder[0]!=inorder[++i]);
            TreeNode* root = new TreeNode(preorder[0]);
            root->left = buildTree( vector<int>(preorder.begin()+1,preorder.begin()+i+1),
                                                    vector<int>(inorder.begin(),inorder.begin()+i) );
            root->right= buildTree( vector<int>(preorder.begin()+i+1,preorder.end()),
                                                    vector<int>(inorder.begin()+i+1,inorder.end()) );
            return root;
        }
    

Log in to reply
 

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