105. Construct Binary Tree from Preorder and Inorder Traversal (M)

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

 

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

 

Constraints:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

A:
就是先通过preorder中的第一个，找到root。  然后，在inorder中找到 其对应的position，  position 左边的就是左子树，  右边的就是右子树。   （相应的范围在preorder中，只需要计算左子树节点的数目，就可以确定。）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return helper(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }
private:
    TreeNode* helper(vector<int>& preorder, int lowP, int highP,
                     vector<int>& inorder, int lowI, int highI) {
        if (lowI >= highI)
            return nullptr;
        TreeNode* root = new TreeNode(preorder[lowP]);
        int ix = lowI;
        for (; ix < highI; ix++)
            if (inorder[ix] == root->val)
                break;
        int nLeft = ix - lowI; // number of nodes in left child
        root->left =
            helper(preorder, lowP + 1, lowP + nLeft + 1, inorder, lowI, ix);
        root->right =
            helper(preorder, lowP + nLeft + 1, highP, inorder, ix + 1, highI);
        return root;
    }
};

犯的错误是：  当nLeftChild的定义搞错了，加了个1.
在计算root.left 和 root.right 的inorder指针的时候，就忘了一个是要-1 , 一个是要+1.  (刚开始，自己是一个没有改，一个+2了）




Mistakes:
1:  主要就是，递归调用的时候， preOrder的low，high参数，要好好考虑。 （尤其是， preorder时， 不需要跳过一个数字的。）