105. Construct Binary Tree from Preorder and Inorder Traversal

ゝ一纸荒年。 2022-05-12 15:16 114阅读 0赞

Given preorder and inorder traversal of a tree, construct the binary tree.

**Note:**  
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
    inorder = [9,3,15,20,7]

Return the following binary tree:

3
       / \
      9  20
        /  \
       15   7

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
           if(preorder.size() == 0 || inorder.size() == 0)
              return NULL;
                  
            int value = preorder[0];
            TreeNode* root = new  TreeNode(value);
            
            vector<int> inorderL;
            vector<int> inorderR;
            bool flag = true;
            int index = 0;
            for(int i = 0; i < inorder.size(); i++)
            {
                if(inorder[i] == value)
                {
                    flag = false;
                    index = i;
                }              
                if(flag)
                    inorderL.push_back(inorder[i]);
                else if(i>index)
                    inorderR.push_back(inorder[i]);
            }
    
            vector<int> preorderL;
            vector<int> preorderR;
            for(int j = 1; j < preorder.size(); j++)
            {
                if(j<index+1)
                    preorderL.push_back(preorder[j]);
                else  
                    preorderR.push_back(preorder[j]);
            }
    
            root->left = buildTree(preorderL,inorderL);
            root->right = buildTree(preorderR,inorderR);
            return root; 
        }
    };