剑指offer 重建二叉树

时间限制：1秒 空间限制：32768K 热度指数：806044

本题知识点： 树

题目描述

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

题目链接：题目链接

这题思路挺清晰，但是自己写不错来，想复杂了。去了讨论区看看，发现原来不用想那么多，直接递归就好了。。。

我们可以来看看，前序和中序的特点，前序的遍历次序为根左右，中序为左根右。即我们可以通过前序找出根，再找出根在中序时遍历的位置i，此时在i前的就为左子树，在i后的为右子树。至于在前序中。。额，感觉有点难说清楚。算了，上代码，上注释，自己推一遍其实就差不多懂了。

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { TreeNode *root = reBinaryTree(pre,0,pre.size()-1,vin,0, vin.size()-1); return root; } //pst，pen分别表示当前子树在前序中的上下边界 //vst，ven分别表示当前子树在中序中的上下边界 TreeNode* reBinaryTree(vector<int> pre,int pst,int pen,vector<int> vin,int vst,int ven) { if (pst > pen || vst > ven){ return NULL; } TreeNode *root = new TreeNode(pre[pst]); for (int i=vst;i<=ven;i++){ if (pre[pst] == vin[i]){ //前序遍历中根的后i-vst属于左子树，中序中根的前i-vst属于左子树 root->left = reBinaryTree(pre,pst+1,pst+i-vst,vin,vst,i-1); root->right = reBinaryTree(pre,pst+i-vst+1,pen,vin,i+1,ven); break; } } return root; } };