輸入一棵二叉樹前序遍歷和中序遍歷的結(jié)果，請重建該二叉樹。二叉樹中每個節(jié)點的值都互不相同；
輸入的前序遍歷和中序遍歷一定合法。
給定：
前序遍歷是：[3, 9, 20, 15, 7]
中序遍歷是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉樹如下所示：
3
/
9 20
/
15 7
遞歸版本比較容易，重點是非遞歸版本
(遞歸) O(n)
遞歸建立整棵二叉樹：先遞歸創(chuàng)建左右子樹，然后創(chuàng)建根節(jié)點，并讓指針指向兩棵子樹。

具體步驟如下：

先利用前序遍歷找根節(jié)點：前序遍歷的第一個數(shù)，就是根節(jié)點的值；
在中序遍歷中找到根節(jié)點的位置 k，則 k左邊是左子樹的中序遍歷，右邊是右子樹的中序遍歷；
假設(shè)左子樹的中序遍歷的長度是 l，則在前序遍歷中，根節(jié)點后面的 l個數(shù)，是左子樹的前序遍歷，剩下的數(shù)是右子樹的前序遍歷；
有了左右子樹的前序遍歷和中序遍歷，我們可以先遞歸創(chuàng)建出左右子樹，然后再創(chuàng)建根節(jié)點；
時間復(fù)雜度分析
我們在初始化時，用哈希表(unordered_map<int,int>)記錄每個值在中序遍歷中的位置，這樣我們在遞歸到每個節(jié)點時，在中序遍歷中查找根節(jié)點位置的操作，只需要 O(1)的時間。此時，創(chuàng)建每個節(jié)點需要的時間是 O(1)，所以總時間復(fù)雜度是 O(n)。
···
class Solution {
public:
unordered_map<int,int> pos;

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = preorder.size();//記錄節(jié)點的個數(shù)，前序和中序的結(jié)果是一樣的
    for (int i = 0; i < n; i ++ )//遍歷開始
        pos[inorder[i]] = i;//把中序遍歷的每個位置用哈希存起來，這樣查找辦成O1，某個值的位置是下標
    return dfs(preorder, inorder, 0, n - 1, 0, n - 1);//前序和中序的起始和終止
}

TreeNode* dfs(vector<int>&pre, vector<int>&in, int pl, int pr, int il, int ir)
{
    if (pl > pr) return NULL;//邊界條件
    int k = pos[pre[pl]] - il;//算出前序遍歷的第一個節(jié)點在中序的位置，就是跟節(jié)點的位置。
    TreeNode* root = new TreeNode(pre[pl]);//重建
    root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1);//PL是跟節(jié)點，+1就是左邊的樹，K是左邊樹的長度，左子樹在中序中是IL起始，K左邊就要減去1
    root->right = dfs(pre, in, pl + k + 1, pr, il + k + 1, ir);
    return root;//右子樹在前序中是開始加跟的后面一個，結(jié)尾是末尾，在中序中是跟后面的
}

};