Simple C++ recursive solution


  • 0
    S

    The trick is to traverse the preorder list, get an element and create a new node, then search for this element in the inorder list. In the inorder list, the elements to the left will be in the left subtree of the node and the ones in the right will be in the right subtree.

    class Solution {
        int i;
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            i = 0;
            return construct(preorder, inorder, 0, preorder.size() - 1);
        }
        
        TreeNode *construct (vector<int>& preorder, vector<int>& inorder, int l, int r){
            if (l > r){ 
                i--;
                return NULL;
            }
            
            TreeNode * root = new TreeNode(preorder[i]);
            
            int j = l;
            int mid;
            while(j <= r){
                if (preorder[i] == inorder[j]){
                    mid = j;
                    break;
                }
                j++;
            }
            
            //i should be common to all
            i++;
            root->left = construct(preorder, inorder, l, mid - 1);     
            i++;
            root->right = construct(preorder, inorder, mid + 1, r);     
                
            return root;    
        }
    };
    

Log in to reply
 

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