面试题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;
}

补充：软件开发 , C++ ,

上一个：面试题6：用两个栈实现队列
下一个：面试题4：从尾到头打印链表