面試題5：重建二叉樹

思路：先根據先序序列第一個數建立根節點，然後再中序序列中找到根節點的位置，進而確定左右子樹的前序序列和後序序列，遞歸的構建左右子樹。

C++代碼：

#include "stdafx.h"   
#include <iostream>   
#include <assert.h>   
using namespace std;  
  
struct BiTreeNode  
{  
    int m_nData;  
    BiTreeNode *m_pLeftChild;  
    BiTreeNode *m_pRightChild;  
};  
  
BiTreeNode* CreateBiTreeByPreorderAndInorder(int* preOrder, int nPreStart, int nPreEnd,  
                                             int* inOrder, int nInStart, int nInEnd)  
{  
    //出口   
    if (nPreStart > nPreEnd)  
    {         
        return NULL;          
    }     
  
    //根據先序序列找到根結點   
    int nRootDate = preOrder[nPreStart];  
    //在中序序列中找到根結點   
    int nCount = 0;  
    int nCur = 0;  
    for (nCur=nInStart; nCur<=nInEnd; nCur++)  
    {  
        if (nRootDate != inOrder[nCur])  
        {  
            nCount++;//nCount記錄左子樹的結點個數   
        }  
        else  
        {  
            break;  
        }  
    }  
  
    assert(nCur >= nInStart && nCur <= nInEnd);     
      
    //創建結點   
    BiTreeNode* pRoot = new BiTreeNode;  
    pRoot->m_nData = nRootDate;    
    //根據中序序列，劃分兩個序列，遞歸處理。   
    pRoot->m_pLeftChild = CreateBiTreeByPreorderAndInorder(preOrder,nPreStart + 1,nPreStart + nCount  
                                                          ,inOrder,nInStart,nInStart + nCount - 1);  
    pRoot->m_pRightChild = CreateBiTreeByPreorderAndInorder(preOrder,nPreStart + nCount + 1,nPreEnd  
                                                          ,inOrder,nInStart + nCount + 1,nInEnd);  
  
    return pRoot;  
}  
  
//根據二叉樹的前序遍歷序列和後序遍歷序列重建二叉樹   
BiTreeNode * CreateBiTreeByPreorderAndInorder(int *preOrder, int *inOrder, int nLength)  
{  
    if ((preOrder!=NULL) && (inOrder!=NULL) && (nLength>0))  
    {  
        return CreateBiTreeByPreorderAndInorder(preOrder, 0, nLength-1, inOrder, 0, nLength-1);  
    }  
    else  
    {  
        return NULL;  
    }  
}  
  
void PreOrderPrint(BiTreeNode *pRoot)  
{  
    if (pRoot != NULL)  
    {  
        cout << pRoot->m_nData << " ";  
        PreOrderPrint(pRoot->m_pLeftChild);  
        PreOrderPrint(pRoot->m_pRightChild);  
    }     
}  
  
void InOrderPrint(BiTreeNode *pRoot)  
{  
    if (pRoot != NULL)  
    {         
        InOrderPrint(pRoot->m_pLeftChild);  
        cout << pRoot->m_nData << " ";  
        InOrderPrint(pRoot->m_pRightChild);  
    }     
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    int nPreOrderArr[8] = {1,2,4,7,3,5,6,8};  
    int nInOrderArr[8] = {4,7,2,1,5,3,8,6};  
    BiTreeNode *pRoot = CreateBiTreeByPreorderAndInorder(nPreOrderArr, nInOrderArr,8);  
  
    cout << "先序序列：";  
    PreOrderPrint(pRoot);  
    cout << endl;  
    cout << "後序序列：";  
    InOrderPrint(pRoot);  
    cout << endl;  
  
    system("pause");  
    return 0;  
}  
#include "stdafx.h"
#include <iostream>
#include <assert.h>
using namespace std;

struct BiTreeNode
{
	int m_nData;
	BiTreeNode *m_pLeftChild;
	BiTreeNode *m_pRightChild;
};

BiTreeNode* CreateBiTreeByPreorderAndInorder(int* preOrder, int nPreStart, int nPreEnd,
											 int* inOrder, int nInStart, int nInEnd)
{
	//出口
	if (nPreStart > nPreEnd)
	{		
		return NULL;		
	}	

	//根據先序序列找到根結點
	int nRootDate = preOrder[nPreStart];
	//在中序序列中找到根結點
	int nCount = 0;
	int nCur = 0;
	for (nCur=nInStart; nCur<=nInEnd; nCur++)
	{
		if (nRootDate != inOrder[nCur])
		{
			nCount++;//nCount記錄左子樹的結點個數
		}
		else
		{
			break;
		}
	}

	assert(nCur >= nInStart && nCur <= nInEnd);	
	
	//創建結點
	BiTreeNode* pRoot = new BiTreeNode;
	pRoot->m_nData = nRootDate;	
	//根據中序序列，劃分兩個序列，遞歸處理。
	pRoot->m_pLeftChild = CreateBiTreeByPreorderAndInorder(preOrder,nPreStart + 1,nPreStart + nCount
		                                                  ,inOrder,nInStart,nInStart + nCount - 1);
	pRoot->m_pRightChild = CreateBiTreeByPreorderAndInorder(preOrder,nPreStart + nCount + 1,nPreEnd
		                                                  ,inOrder,nInStart + nCount + 1,nInEnd);

	return pRoot;
}

//根據二叉樹的前序遍歷序列和後序遍歷序列重建二叉樹
BiTreeNode * CreateBiTreeByPreorderAndInorder(int *preOrder, int *inOrder, int nLength)
{
    if ((preOrder!=NULL) && (inOrder!=NULL) && (nLength>0))
    {
		return CreateBiTreeByPreorderAndInorder(preOrder, 0, nLength-1, inOrder, 0, nLength-1);
    }
	else
	{
		return NULL;
	}
}

void PreOrderPrint(BiTreeNode *pRoot)
{
	if (pRoot != NULL)
	{
		cout << pRoot->m_nData << " ";
		PreOrderPrint(pRoot->m_pLeftChild);
		PreOrderPrint(pRoot->m_pRightChild);
	}	
}

void InOrderPrint(BiTreeNode *pRoot)
{
	if (pRoot != NULL)
	{		
		InOrderPrint(pRoot->m_pLeftChild);
		cout << pRoot->m_nData << " ";
		InOrderPrint(pRoot->m_pRightChild);
	}	
}

int _tmain(int argc, _TCHAR* argv[])
{
	int nPreOrderArr[8] = {1,2,4,7,3,5,6,8};
	int nInOrderArr[8] = {4,7,2,1,5,3,8,6};
	BiTreeNode *pRoot = CreateBiTreeByPreorderAndInorder(nPreOrderArr, nInOrderArr,8);

	cout << "先序序列：";
	PreOrderPrint(pRoot);
	cout << endl;
	cout << "後序序列：";
	InOrderPrint(pRoot);
	cout << endl;

	system("pause");
	return 0;
}