二叉樹面試題（一） 重建二叉樹

問題描述：

由前序周遊和中序周遊重建二叉樹（前序序列：1 2 3 4 5 6 - 中序序列:3 2 4 1 6 5）資料不含重複值。

題目分析如下：

前序周遊序列1 2 3 4 5 6，前序周遊規則是根--左--右。

中序周遊序列3 2 4 1 6 5，中序周遊規則是左--根--右

1.由前序周遊可知根節點一定為第一個元素1，在中序周遊序列中找到1對應位置，判斷根節點1的左右子樹是否為空，1的左右都不為空，1的左邊就是左子樹324，右邊就是右子樹56；

2.再根據前序周遊規則可知，左子樹序列裡第一個就是左子樹的根節點2，右子樹序列裡的第一個就是右子樹的根節點5，用上次的方法遞歸建立左右子樹。

3.再根據中序周遊序列可知，左子樹的根節點2左邊的一定是以其為根節點的左子樹序列3，右邊就是以其為根節點的右子樹序列4，

右子樹的根節點5左邊的一定是以其為根節點的右子樹序列6，直至序列為空，就可以完整重建二叉樹了

代碼實作：

#include<iostream>
#include<cassert>
using namespace std;
struct NewTreeNode
{
	NewTreeNode* _left;
	NewTreeNode* _right;
	int _value;
	NewTreeNode(int value)
		:_value(value)
		,_left(NULL)
		,_right(NULL)
	{}
};


typedef NewTreeNode Node;

  
Node* _RebuildTree(int *startPre,int *endPre,int *startIn,int *endIn)  
{   
    Node *root = new Node(startPre[0]); 
	//_left和_right已初始化為NULL
    if(startIn == endIn && *startIn == *startIn)  
    {  
        return root;  
    }  
    //4.根據此根節點在中序中找此節點的位置  
    int * rootIn = startIn;  
    while(*startPre != *rootIn)  
    {  
        rootIn++;  
    }  
    //根據此根節點在中序周遊中的位置，遞歸還原左子樹  
    int leftlen = rootIn-startIn;  
    if(leftlen>0)  
    {  
        root->_left = _RebuildTree(startPre+1,startPre+leftlen,startIn,startIn+leftlen-1);  
  
    }  
    if(leftlen+startIn < endIn)//該節點還存在右子樹，是以繼續遞歸還原右子樹  
    {//遞歸還原右子樹  
        root->_right = _RebuildTree(startPre+leftlen+1,endPre,startIn+leftlen+1,endIn);  
    }  
    return root;  
}

Node*  RebuildTree(int* PreOrder,int* InOrder,int len)  
{  
    if(PreOrder == NULL || InOrder == NULL )  
        return NULL;    
    else    
        return _RebuildTree(PreOrder,PreOrder+len-1,InOrder,InOrder+len-1);  
}  

void PostOrder(Node *root)  
{  
	if(root->_left != NULL)  
		PostOrder(root->_left); 

	if(root->_right != NULL)  
		PostOrder(root->_right);  

	cout<<root->_value<<" ";  
}  
void PrevOrder(Node *root)  
{  
	if(root==NULL)
		return;
	cout<<root->_value<<" ";
	if(root->_left != NULL)  
		PrevOrder(root->_left); 

	if(root->_right != NULL)  
		PrevOrder(root->_right);    
}  


int main()  
{  
    int PreOrder[] = {1,2,3,4,5,6};  
    int InOrder[] = {3,2,4,1,6,5};  
    int PreSize=sizeof(PreOrder)/sizeof(PreOrder[0]);
    int InSize=sizeof(InOrder)/sizeof(InOrder[0]);
	if(PreSize!=InSize)
	{
		cout<<"所給資料錯誤"<<endl;
		return -1;
	}
    NewTreeNode* root = RebuildTree(PreOrder,InOrder,PreSize);  
	PrevOrder(root);//123456
    cout<<endl; 

    PostOrder(root);//342651  
    cout<<endl;  
	 
    system("pause");  
    return 0 ;  
}
           

在此運用前序和後序檢查該樹是否正确

運作結果：

                        未完，後續還有部分關于二叉樹面試題！待續！