剑指offer 面试题6：重建二叉树-白红宇

题目

　　输入某二叉树的前序遍历和中序遍历，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含有重复的数字。

　　例如，前序遍历序列：｛1，2，3，7，3，5，6，8｝，中序遍历序列：｛4，7，2，1，5，3，8，6｝

答案

　　前序遍历：

　　　　前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

　　中序遍历：

　　　　中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。

#include 
      
       using namespace std;struct binary_tree_node{    int value;    binary_tree_node*  left;    binary_tree_node*  right;};binary_tree_node* binary_tree_constuct(int* preorder, int* inorder, int length);int main(){    int pre[8] = {
    1,2,4,7,3,5,6,8};    int in[8]  = {
    4,7,2,1,5,3,8,6};    binary_tree_node* root = binary_tree_constuct(pre, in, 8);}binary_tree_node* construct_method(int* preorder, int* endpreorder, int* inorder, int* endinorder){    int root_value = preorder[0];    binary_tree_node* root = new binary_tree_node();    root->left = NULL;    root->right = NULL;    cout<
       
        <<" ";    if(preorder == endpreorder && inorder == endinorder)        return root;    int* rootIndex = preorder;    rootIndex++;    while(*rootIndex != root_value && rootIndex < endpreorder)        rootIndex++;    int left_len = rootIndex - preorder;    int* left_preorder_end = preorder + left_len;    //left    if(left_len > 0)    {        root->left = construct_method(preorder+1, left_preorder_end, inorder, rootIndex-1);    }    //right    if(left_len < endpreorder - preorder)    {        root->right = construct_method(left_preorder_end+1, endpreorder, rootIndex+1, endinorder);    }    return root;}binary_tree_node* binary_tree_constuct(int* preorder, int* inorder, int length){    if(preorder == NULL || inorder == NULL || length <= 0)    {        return NULL;    }    return construct_method(preorder, preorder+length-1, inorder,inorder+length-1);}

本文由创作，采用进行许可。欢迎转载，请注明出处：
转载自：