剑指office--------重建二叉树

题目描述

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

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
13         if (pre.size()==0||vin.size()==0)    return nullptr;
14         TreeNode *Head=new TreeNode(pre[0]);
15         int len=pre.size(),rt;
16         vector<int>pre1,vin1,pre2,vin2;
17         for (int i=0;i<len;i++){
18             if (vin[i]==pre[0]){
19                 rt=i;
20                 break;
21             }
22         }
23         for (int i=0;i<rt;i++){
24             pre1.push_back(pre[i+1]);
25             vin1.push_back(vin[i]);
26         }
27         for (int i=rt+1;i<len;i++){
28             pre2.push_back(pre[i]);
29             vin2.push_back(vin[i]);
30         }
31         Head->left=reConstructBinaryTree(pre1,vin1);
32         Head->right=reConstructBinaryTree(pre2, vin2);
33         return Head;
34     }
35 };

特点：

前序遍历中，第一个数便是根结点，

中序遍历中，结点的右边是其的右子树，左边则是左子树。

两者相连，例：

前序遍历序列{1,2,4,7,3,5,6,8} pre

中序遍历序列{4,7,2,1,5,3,8,6} vin　

4 7 2是1的右子树，在先序遍历中，对应的是2,4,7,

边界：vin【0】与vin【2】　　对应区间{4,7,2}

边界：pre【1】与pre【3】对应区间{2,4,7}

对应关系就是左子树的前序遍历比中序遍历快一单位。

右子树边界则相同， vin【4】与vin【7】对应区间{5,3,8,6}

　　　　　　　　　　pre【4】与pre【7】对应区间{3,5,6,8}