面试题7——二叉树重建

题目：输入某一个二叉树的前序和中序遍历，重建该二叉树，返回二叉树的根节点
面试题7——二叉树重建
#include<stdio.h>
#include<assert.h>
#include<malloc.h>
typedef int DataType;

typedef struct BinTreeNode{
  struct BinTreeNode *pLeft;
  struct BinTreeNode *pRight;
  DataType data;
}BinTreeNode;

//创建节点
BinTreeNode *BuyNode(DataType data)
{
  BinTreeNode *NewNode = (BinTreeNode *)malloc(sizeof(BinTreeNode));
  assert(NewNode);
  NewNode->data = data;
  NewNode->pLeft = NULL;
  NewNode->pRight = NULL;
  return NewNode;
}
//重建二叉树
BinTreeNode *_CreateBinTree(int *pre_start,int *pre_end,int *in_start,int *in_end)
{
  BinTreeNode *root = BuyNode(pre_start[0]);
  //判断只是一个节点
  if(pre_start == pre_end)
  {
    if(in_start == in_end && *pre_start == *in_start)
    {
      //printf("只有一个节点\n");
      return root;
    }
    else 
    {
      //printf("invalid input\n");
      return NULL;
    }
  }
  //多个节点
  //1.找中序遍历中头结点出现的位置
  //2.判断头结点在中序遍历中是否存在以及合法
  int *cur = in_start;
  while(*cur != *pre_start && cur != in_end)
    cur++;
  if(cur == in_end && *pre_start != *cur)
  {
    //printf("invalid input\n");
    return NULL;
  }
  else 
  {
    //LeftChildSize表示根节点在中序遍历中下标的位置
    int LeftChildSize = cur-in_start;
    int *PreChildEnd = pre_start+LeftChildSize;
    if(LeftChildSize>0)
      root->pLeft =  _CreateBinTree(pre_start+1,PreChildEnd,in_start,cur-1);

    if(LeftChildSize<pre_end-pre_start)
      root->pRight =  _CreateBinTree(PreChildEnd+1,pre_end,cur+1,in_end);
  }
  return root;
}

//封装一个函数
BinTreeNode *CreateBinTree(int *pre_arr,int *in_arr,int size)
{
  if(pre_arr == NULL || in_arr == NULL || size<=0)
  {
    printf("invalid input\n");
    return NULL;
  }
  return _CreateBinTree(pre_arr,pre_arr+size-1,in_arr,in_arr+size-1);
}

//前序打印
void PreOrder(BinTreeNode *root)
{
  if(root)
  {
    printf("%d ",root->data);
    PreOrder(root->pLeft);
    PreOrder(root->pRight);
  }
}

int main()
{
  int pre_arr[] = {1,2,4,7,3,5,6,8};
  int in_arr[] = {4,7,2,1,5,3,8,6};
  int pre_size = sizeof(pre_arr)/sizeof(int);
  int in_size = sizeof(in_arr)/sizeof(int);
  if(pre_size != in_size)
  {
    printf("invalid input\n");
    return 1;
  }
  BinTreeNode *Node = CreateBinTree(pre_arr,in_arr,pre_size);
  PreOrder(Node);
  printf("\n");
  return 0;
}
面试题7——二叉树重建

相关推荐
