【面试题】剑指offer06--重建二叉树

ゞ浴缸里的玫瑰 2022-06-14 07:40 106阅读 0赞

我们都知道，二叉树有很多种，单单给定某一个序列，是不能将二叉树确定出来的，因此需要重建二叉树

重建二叉树的定义就是，给定一个树的前序和中序，将这棵二叉树重新建好

步骤为：

1、前序遍历的第一个节点即为根节点

2、根据根节点，在中序遍历中找出左子树和右子树，并统计左子树和右子树的个数

3、递归构建左子树和右子树

以下是代码的实现：

#include<iostream>
    using namespace std;
    #include<assert.h>
    
    
    struct TreeNode//定义一个树的结构体
    {
    	int value;//定义树的值
    
    	TreeNode* left;//定义树的左孩子
    	TreeNode* right;//定义树的右孩子
    	TreeNode(int data)
    		:value(data)
    		, left(NULL)
    		, right(NULL)
    	{
    	}
    };
    
    typedef TreeNode Node;
    
    Node* ReConstruct(int *preorder, int *inorder, int length)
    {
    	assert(preorder);
    	assert(inorder);
    
    	if (length <= 0)
    	{
    		return NULL;
    	}
    
    	Node* root = new Node(*preorder);
    	int* pre_tmp = preorder;
    	int* in_tmp = inorder;
    	int leftTreeNum = 0;
    	int len = length;
    
    	while (*in_tmp != *preorder)
    	{
    		leftTreeNum++;
    		in_tmp++;
    		pre_tmp++;
    		len--;
    
    		if (len == 1 && *in_tmp != *preorder)
    		{
    			throw string("前序遍历和中序遍历异常！");
    		}
    	}
    
    	int* leftPreOrder = preorder + 1;
    	int* rightPreOrder = pre_tmp + 1;
    	int* leftOrder = inorder;
    	int* rightOrder = in_tmp + 1;
    	int rightTreeNum = length - leftTreeNum - 1;
    
    	root->left=ReConstruct(leftPreOrder, leftOrder, leftTreeNum);
    	root->right = ReConstruct(rightPreOrder, rightOrder, rightTreeNum);
    
    	return root;
    }
    
    void InOrderPrint(Node* root)
    {
    	if (root == NULL)
    	{
    		return;
    	}
    	InOrderPrint(root->left);
    	cout << root->value << " ";
    	InOrderPrint(root->right);
    }
    
    void Test()
    {
    	const int M = 10;
    	const int PreOrder[M] = { 1, 2, 4, 8, 9, 5, 10, 3, 6, 7 };
    	const int InOrder[M] = { 8, 4, 9, 2, 5, 10, 1, 6, 3, 7 };
    
    	int* preorder = const_cast<int*>(PreOrder);
    	int* inorder = const_cast<int*>(InOrder);
    	Node* root = ReConstruct(preorder, inorder, M);
    	InOrderPrint(root);
    	cout << endl;
    }
    int main()
    {
    	Test();
    	system("pause");
    	return 0;
    }