剑指offer编程题_重建二叉树

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

题解：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//输出数组元素
void display(vector<int> array);

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

/*解题思路
1.先求出根节点：根据前序遍历的性质，前序遍历序列的第一个元素就是树的根节点；
2.求出左右子树节点的范围：根据后序遍历的性质，后序遍历序列中根节点左边的
序列就是树的左子树的中序遍历序列，其右边的序列就是树的右子树的中序遍历序列；
3.通过左右子树的中序序列元素集合带入前序遍历序列可以求出左右子树的前序序列；
4.左右子树的前序序列第一个元素分别是根节点的左右孩子；
5.求出了左右子树的前序和中序遍历序列可以递归以上步骤。
*/
class Solution{
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in)
    {
        if(pre.size()==0)
            return NULL;
        //根据前序遍历的性质，前序遍历序列的第一个元素就是树的根
        TreeNode *root=new TreeNode(pre[0]);
        if(pre.size()==1)
            return root;
        int rootindex; //根节点在中序遍历序列中位置下标
        int i;
        for(i=0;i<in.size();++i){
            if(in[i]==pre[0]){
                rootindex=i;
                break;
            }
        }
        //vector数组的初始化可以通过其他容器的迭代器完成
        vector<int> pre_left(pre.begin()+1,pre.begin()+rootindex+1); //前序左子树
        vector<int> pre_right(pre.begin()+rootindex+1,pre.end()); //前序右子树
        vector<int> in_left(in.begin(),in.begin()+rootindex); //中序左子树
        vector<int> in_right(in.begin()+rootindex+1,in.end()); //中序右子树
        //将左右子树安到root的左右指针上
        root->left=reConstructBinaryTree(pre_left,in_left);
        root->right=reConstructBinaryTree(pre_right,in_right);
        return root;
    }
};

void preTraverse(TreeNode *T)
{
    if(T){
        printf("%d ",T->val);
        preTraverse(T->left);
        preTraverse(T->right);

    }
    //printf("\n");
}

void inorderTraverse(TreeNode *T)
{
    if(T){
        inorderTraverse(T->left);
        printf("%d ",T->val);
        inorderTraverse(T->right);
    }
    //printf("\n");
}

int main(int argc,char **argv)
{
    int p[]={1,2,4,7,3,5,6,8};
    int i[]={4,7,2,1,5,3,8,6};
    vector<int> pre(p,p+8);
    vector<int> in(i,i+8);
    printf("先序遍历结果：");
    display(pre);
    printf("中序遍历结果：");
    display(in);
    Solution sol;
    TreeNode *t=sol.reConstructBinaryTree(pre,in);
    printf("重构二叉树的先序遍历结果：");
    preTraverse(t);
    printf("\n");
    printf("重构二叉树的中序遍历结果：");
    inorderTraverse(t);
    return 0;
}

void display(vector<int> array)
{
    int i;
    for(i=0;i<array.size();++i){
        printf("%d ",array[i]);
    }
    printf("\n");
}

运行结果