重建二叉树

原题链接 重建二叉树

题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

首先总结一下前序、中序、后序三种遍历方式的特性：

• 前序遍历
  前序遍历首先访问根节点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。
  1 访问根节点。
  2 前序遍历左子树。
  3 前序遍历右子树。
  需要注意的是：遍历左右子树时仍然采用前序遍历法。

  前序遍历 如图所示二叉树，前序遍历结果: ABDECF

• 中序遍历
  中序遍历首先遍历左子树，然后访问根节点，最后遍历右子树。
  1 中序遍历左子树。
  2 访问根节点。
  3 中序遍历右子树。
  

  中序遍历 如图所示二叉树，中序遍历结果为：DBEAFC

• 后序遍历
  后序遍历首先遍历左子树，然后遍历右子树，最后访问根节点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历跟节点。
  1 后序遍历左子树。
  2 后序遍历右子树。
  3 访问根节点
  

  后序遍历 如图所示二叉树，后序遍历结果为: DEBFCA

重建二叉树：前序+中序，后续+中序可以完成重建，而前序+后序无法完成

思路链接：根据前序第一个字符是根的特性，再在中序中找到这个位置，分开，左边的是左子树，右边的是右子树。然后递归求出结果。

代码如下：

#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");
}