剑指offer之面试题6重建二叉树

待我称王封你为后i 2022-08-22 01:29 113阅读 0赞

**问题描述**：

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

例如：

输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树如下，并返回它的头结点。

![20160510204800437][]

**实现代码**如下：

#include<stdio.h>
    #include<stdlib.h>
    
    struct BinaryTreeNode{
    	int value;
    	struct BinaryTreeNode *left;
    	struct BinaryTreeNode *right;
    };
    
    struct BinaryTreeNode *construct(int *preOrder,int *inOrder,int length);
    struct BinaryTreeNode *constructCore(int *startPreOrder,int *endPreOrder,int *startInOrder,int *endInOrder);
    //前序遍历 
    void showPreOrder(struct BinaryTreeNode *root){
    	if(root !=NULL){
    		printf("%d\t",root->value);
    		showPreOrder(root->left);
    		showPreOrder(root->right);
    	}
    }
    //中序遍历 
    void showInOrder(struct BinaryTreeNode *root){
    	if(root !=NULL){
    		int value=root->value;
    		showInOrder(root->left);
    		printf("%d\t",root->value);
    		showInOrder(root->right);
    	}
    }
    
    int main(){
    	int pre[]={
    		1,2,4,7,3,5,6,8
    	};
    	int *preOrder=pre;
    	int in[]={
    		4,7,2,1,5,3,8,6
    	};
    	int *inOrder=in;
    	struct BinaryTreeNode *root=construct(preOrder,inOrder,8);
    	struct BinaryTreeNode *show=root;
    	printf("this is preOrder!\n");
    	showPreOrder(show);
    	printf("\nthis is inOrder!\n");
    	showInOrder(show);
    	printf("\n");
    	return 0;
    }
    
    //重建 
    struct BinaryTreeNode *construct(int *preOrder,int *inOrder,int length){
    	if(preOrder==NULL || inOrder == NULL || length<=0){
    		return NULL;
    	}
    	return constructCore(preOrder,preOrder+length-1,inOrder,inOrder+length-1);
    }
    //重建的实现代码 
    struct BinaryTreeNode *constructCore(int *startPreOrder,int *endPreOrder,int *startInOrder,int *endInOrder){
    	struct BinaryTreeNode *root = (struct BinaryTreeNode *)malloc(sizeof(struct BinaryTreeNode));
    	int rootValue=startPreOrder[0];
    	root->value=rootValue;
    	root->left=root->right=NULL;
    	
    	if(startPreOrder==endPreOrder){
    		if(startInOrder==endInOrder){
    			return root;
    		}else{
    			return NULL;
    		}
    	}
    	int *rootInOrder=startInOrder;
    	while(*rootInOrder!=rootValue && rootInOrder!=endInOrder)
    		++rootInOrder;
    	if(*rootInOrder!=rootValue && rootInOrder==endInOrder)return NULL;
    	int length =rootInOrder-startInOrder;
    	int *leftPreOrderEnd = startPreOrder+length;
    	if(length>0){
    		//build left tree
    		root->left=constructCore(startPreOrder+1,leftPreOrderEnd,startInOrder,rootInOrder-1);
    	}
    	if(length< endPreOrder-startPreOrder){
    		//build right tree
    		root->right=constructCore(leftPreOrderEnd+1,endPreOrder,rootInOrder+1,endInOrder);
    	}
    	return root;
    }

这个算法的时间复杂度与结点个数n正相关：O(n)。

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51366400  
**作者**：WSYW126

[20160510204800437]: /images/20220724/6d5042633e8648eeb78eb96e7b70f08b.png