面试题7：重建二叉树

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

#include <iostream> #include <string> #include <cstdlib> using namespace std; typedef struct treenode { int val; treenode* lchild; treenode* rchild; }TreeNode, *Tree; Tree constructTree(int* startPreOrder, int* endPreOrder, int* startInorder, int* endInorder) { int rootVal = *startPreOrder; Tree root = new TreeNode; root->val = rootVal; root->lchild = nullptr; root->rchild = nullptr; if (startPreOrder == endPreOrder) { if (startInorder == endInorder && *startPreOrder == *startInorder) return root; else throw std::exception("Input Invalid"); } int* rootInoder = startInorder; while (rootInoder <= endInorder && *rootInoder != rootVal) rootInoder++; if (rootInoder == endInorder && *rootInoder != rootVal) throw std::exception("Input Invaild"); int leftLength = rootInoder - startInorder; int* leftEndProOrder = startPreOrder + leftLength; if (leftLength > 0) { root->lchild = constructTree(startPreOrder + 1, leftEndProOrder, startInorder, rootInoder - 1); } if (leftLength < endPreOrder - startPreOrder) { root->rchild = constructTree(leftEndProOrder + 1, endPreOrder, rootInoder + 1, endInorder); } return root; } int main() { int preorder[8] = { 1, 2, 4, 7, 3, 5, 6, 8 }; int inorder[8] = { 7, 4, 2,1, 5, 3, 8, 6 }; Tree root = constructTree(preorder, preorder + 7, inorder, inorder + 7); }