Uva548(二叉树通过中序和后序遍历数据创建树)

通过中序和后序遍历创建出树

最难的就是这部分啦，下面我讲讲我的思路，
首先明确中序和后序遍历的特点：
中序：根节点在左右子树中间
后序：根节点在左右子树最后
那我们就可以根据后序节点找到根节点，在通过遍历中序的数据，找到根节点下面的左右子树，就这样不断去构造树
例如：

图画的不好，看不清建议放大

代码

#include <stdio.h>
#include <stack>
#include <iostream>
#include <time.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<int> v1;
vector<int> v2;
int t;
struct node
{
	int val;
	node* lnode;
	node* rnode;
	node(int val)
	{
		this->val = val;
		 lnode=NULL;
		 rnode=NULL;
	}
};
node* Root = NULL;
node* creat(node* root,int begin,int end,int n) {//n为根节点在v2上的索引
	if (begin > end)
		return NULL;
	if (root == NULL)
		root = new node(0);
	int begin1, begin2, end1, end2;//用begin1和end1来记录左子树的在v1上的区间，用begin2和end2来记录右子树的在v1区间
	for (int i = begin; i <= end; i++) {
		if (v1[i] == v2[n])
		{
			begin1 = begin;
			end1 = i - 1;
			begin2 = i + 1;
			end2 = end;
			break;
		}
	}
	root->val = v2[n];
	root->lnode=creat(root->lnode, begin1, end1, n - (end2 - begin2 + 2));//递归创建左右树
	root->rnode=creat(root->rnode, begin2, end2, n -1);
	return root;
}
int search(node* root,int &number) {//用number来记录下面选择的叶子的权值
	int sum=0; sum += root->val;
	int m=20000; int n=20000;
	int number1, number2;
	if (root->lnode == NULL&&root->rnode == NULL) {//是叶子
		number = root->val;
	}
	if (root->lnode != NULL&&root->rnode != NULL) {//后面的都是分类，对于每一种情况都分了类
		n = search(root->lnode, number1);
		m = search(root->rnode, number2);
		if (m < n) {
			number = number2;
			sum += m;
		}
		if (m > n) {
			number = number1;
			sum += n;
		}
		if (m == n && number1 > number2)
		{
			number = number2;
			sum +=m ;
		}
		if (m == n && number1 < number2)
		{
			number = number1;
			sum += n;
		}
	}
	if (root->rnode!=NULL && root->lnode==NULL)
	{
		m = search(root->rnode, number2);
		sum += m;
		number = number2;
	}
	if (root->lnode != NULL && root->rnode == NULL)
	{
		n= search(root->lnode, number1);
		sum += n;
		number = number1;
	}
	return sum;
}
int main(void) {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int m;
		cin >> m;
		v1.push_back(m);
	}
	for (int i = 0; i < n; i++) {
		int m;
		cin >> m;
		v2.push_back(m);
	}
	Root=creat(Root, 0, n - 1, n - 1);
	int sum = 0;
	sum = search(Root, t);
	cout << sum << " "<< t;
	system("pause");
}