二叉树的构造

二叉树不同的遍历方式会有着不同的遍历序列，如何更具不同的遍历序列构造出二叉树呢？

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

1，前序序列+,中续序列->二叉树

无重复数据的二叉树的构造

前序：1,2,3,4,5,6

中序：2,3,1,5,4,6

在二叉树的前序遍历中，第一个数字总是树的根节点的值，但在中序遍历中，根节点的值在序列中间，左子树的节点位于根节点的值的左边，而右子树的节点在根节点右边。

 1 void BuildTreeFromPre(TreeNode **tree,vector<int> pre,vector<int>mid){
 2     if(pre.size()==0||mid.size() == 0) return;
 3     *tree = new TreeNode(pre[0]); //构建根节点
 4     //在中序遍历找根节点
 5     int i = 0;
 6     for(i = 0;i<mid.size()&&mid[i]!=pre[0];i++);
 7     vector<int> preleft(pre.begin()+1,pre.begin()+i+1);
 8     vector<int> preright(pre.begin()+i+1,pre.end());
 9     vector<int> midleft(mid.begin(),mid.begin()+i);
10     vector<int> midright(mid.begin()+i+1,mid.end());
11     //构造左子树
12     BuildTreeFromPre( &((*tree)->left),preleft,midleft);
13     //构造右子树
14     BuildTreeFromPre( &((*tree)->right),preright,midright);
15 }

具有重复数据的二叉树的构造

前序：1,1,3,4,5,6

后续：1,3,1,5,4,6

在前序遍历中，第一个数字依然还是树的根节点，然后，在中序遍历中，可能会出现多个值与根节点相同的值，此时根据值来判断是否为根节点是行不通的。

若在中序序列中，节点i为根节点，它将中序序列分割成左子树和右子树的中序序列。根据这些信息前序序列也可以分成左子树和右子树的前序遍历，而对于同样一棵树的前序遍历和后序遍历，元素的内容是一样的，只是顺序不同而已，也就是说他们的异或和是相等的，根据这个特点我们可以确定中序序列中的根节点。

 1 bool isRoot(vector<int> &pre,vector<int>&mid,int i){
 2     int j;
 3     int sum1 = 0,sum2=0;
 4     for(j=1;j<=i;j++){
 5         sum1 ^=pre[j];
 6     }
 7     for(j=0;j<i;j++){
 8         sum2 ^=mid[j];
 9     }
10     return sum1==sum2;
11 }
12 void BuildTreeFromPre(TreeNode **tree,vector<int> pre,vector<int>mid){
13     if(pre.size()==0||mid.size() == 0) return;
14     *tree = new TreeNode(pre[0]); //构建根节点
15     //在中序遍历找根节点
16     bool findRoot=false;
17     int i = 0;
18     while(!findRoot){
19         for(i = 0;i<mid.size()&&mid[i]!=pre[0];i++);
20         if(isRoot(pre,mid,i)){
21          findRoot = true;
22         }
23     }
24     vector<int> preleft(pre.begin()+1,pre.begin()+i+1);
25     vector<int> preright(pre.begin()+i+1,pre.end());
26     vector<int> midleft(mid.begin(),mid.begin()+i);
27     vector<int> midright(mid.begin()+i+1,mid.end());
28     //构造左子树
29     BuildTreeFromPre( &((*tree)->left),preleft,midleft);
30     //构造右子树
31     BuildTreeFromPre( &((*tree)->right),preright,midright);
32     
33 }

需要提醒的是，具有重复数据的前序和中序遍历序列，并不能保证构成唯一的树结构，就像上面的例子，中序遍历的第一个元素和第3个元素作为根节点都是合法的。

上面的实现的递归函数中，参数列表中都有vector向量，每次递归前都需要构造vector变量，势必会早造成额外的开销，一种改进的方式可以用向量的首尾迭代器和下标来表示有效的vector范围

2，后序序列+中序序列->二叉树

后续遍历的原理根前序遍历相同

 1 void BuildTreeFromPost(TreeNode **tree,vector<int>::iterator postBegin,vector<int>::iterator postEnd,
 2                        vector<int>::iterator midBegin,vector<int>::iterator midEnd){
 3     if(postBegin == postEnd || midBegin == midEnd) return;
 4     vector<int>::iterator p = postEnd;
 5     *tree = new TreeNode(*(p-1));
 6     for(p = midEnd; p>midBegin && *(p-1)!=*(postEnd-1);p--);
 7     BuildTreeFromPost(&(*tree)->left,postBegin,postBegin+(p-midBegin-1),midBegin,p-1);
 8     BuildTreeFromPost(&(*tree)->right,postBegin+(p-midBegin-1),postEnd-1,p,midEnd);
 9 }
10 
11 void BuildTreeFromPost(TreeNode **tree,vector<int>post,vector<int>mid){
12     BuildTreeFromPost(tree,post.begin(),post.end(),mid.begin(),mid.end());
13 }

3，层序序列

层序：1,2,4,#,3,5,6; 从每一层读取，没有元素的位置用#补上，倘若所有元素都是正整数，#可用负数代替，利用每个元素和其后代元素的位置关系构造二叉树

void BuildTree(TreeNode **tree,vector<int> vals){
  if(vals.size() == 0) return;
  TreeNode *nodes = new TreeNode[vals.size()];//创建n个节点
  for(int i=0;i<vals.size();i++){//建立这些节点的关系
      (nodes+i)->val = vals[i];
      if(2*i+1<vals.size() && vals[2*i+1]>-1){ //如果其有左孩子
           (nodes+i)->left = (nodes+2*i+1);
      }
      if(2*i+2<vals.size() && vals[2*i+2] > -1){//如果其有右孩子
           (nodes+i)->right = nodes+2*i+2;
      }
  }
  *tree = nodes;
}

Bingo,go,go,go!