原題鏈接 重建二叉樹

題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹倒庵。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}巾陕，則重建二叉樹并返回琳钉。

首先總結一下前序、中序戳表、后序三種遍歷方式的特性：

• 前序遍歷
  前序遍歷首先訪問根節(jié)點然后遍歷左子樹桶至，最后遍歷右子樹。在遍歷左匾旭、右子樹時镣屹，仍然先訪問根節(jié)點，然后遍歷左子樹价涝，最后遍歷右子樹女蜈。
  1 訪問根節(jié)點。
  2 前序遍歷左子樹色瘩。
  3 前序遍歷右子樹伪窖。
  需要注意的是：遍歷左右子樹時仍然采用前序遍歷法。

  前序遍歷
  如圖所示二叉樹居兆，前序遍歷結果: ABDECF

• 中序遍歷
  中序遍歷首先遍歷左子樹覆山，然后訪問根節(jié)點，最后遍歷右子樹泥栖。
  1 中序遍歷左子樹簇宽。
  2 訪問根節(jié)點。
  3 中序遍歷右子樹吧享。
  

  中序遍歷
  如圖所示二叉樹晦毙，中序遍歷結果為：DBEAFC

• 后序遍歷
  后序遍歷首先遍歷左子樹，然后遍歷右子樹耙蔑，最后訪問根節(jié)點见妒，在遍歷左、右子樹時，仍然先遍歷左子樹须揣，然后遍歷右子樹盐股，最后遍歷跟節(jié)點。
  1 后序遍歷左子樹耻卡。
  2 后序遍歷右子樹疯汁。
  3 訪問根節(jié)點
  

  后序遍歷
  如圖所示二叉樹，后序遍歷結果為: DEBFCA

重建二叉樹：前序+中序卵酪，后續(xù)+中序可以完成重建幌蚊，而前序+后序無法完成

思路鏈接：根據(jù)前序第一個字符是根的特性，再在中序中找到這個位置溃卡，分開溢豆，左邊的是左子樹，右邊的是右子樹瘸羡。然后遞歸求出結果漩仙。

代碼如下：

#include<iostream>
#include<vector>

using namespace std;


struct TreeNode
{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};

struct TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
    int length = vin.size();
    if (length == 0) {
        return NULL;
    }
    
    TreeNode* head = new TreeNode(pre[0]);
    vector<int> left_pre, right_pre;
    vector<int> left_in, right_in;
    int index = 0;
    for (int i = 0;i < vin.size();i++) {
        try {
            if (pre[0] == vin[i]) {
                index = i;
                break;
            }
            else {
                throw "INPUT Valid";
            }
        }
        catch (const char* msg) {
            cout << msg << endl;
        }
    }

    for (int i = 0;i < index;i++) {
        left_pre.push_back(pre[i + 1]);
        left_in.push_back(vin[i]);
    }
    for (int j = index + 1;j < length;j++) {
        right_pre.push_back(pre[j]);
        right_in.push_back(vin[j]);
    }
    head->left = reConstructBinaryTree(left_pre, left_in);
    head->right = reConstructBinaryTree(right_pre, right_in);

    return head;
}

void main() {
    vector<int> pre = { 1,2,4,7,3,5,6,8 };
    vector<int> vin = { 4,7,2,10,5,3,8,6 };

    TreeNode* res = reConstructBinaryTree(pre, vin);

    system("pause");
}