【挑战程序设计天梯赛】树与二叉树专题训练

第一章 二叉树题型总结

针对团体程序设计天梯赛几乎年年必考的分值为25分的二叉树题目，本文带你玩转二叉树，逢二叉树则秒杀之，让二叉树不再成为难题，而是你的送分题！

题型Ⅰ 已知后序中序求先序 题目描述及分析（手稿）

AC代码（引用自柳婼）

#include 
using namespace std;
int post[] = {3, 4, 2, 6, 5, 1};
int in[] = {3, 2, 4, 1, 6, 5};
void pre(int root, int start, int end) {
    if(start > end) return ;
    int i = start;
    while(i < end && in[i] != post[root]) i++;
    printf("%d ", post[root]);
    pre(root - 1 - end + i, start, i - 1);
    pre(root - 1, i + 1, end);
}
 
int main() {
    pre(5, 0, 5);
    return 0;
}

题型Ⅱ 已知后序中序求层序 分析

与后序中序转换为前序的代码相仿（无须构造二叉树再进行广度优先搜索～），只不过加一个变量index，表示当前的根结点在二叉树中所对应的下标（从0开始），所以进行一次输出先序的递归过程中，就可以把根结点下标index及所对应的值存储在map level中，map是有序的会根据index从小到大自动排序，这样递归完成后level中的值就是层序遍历的顺序
——柳婼

AC代码（引用自柳婼）

不愧是PAT甲级满分选手的代码，简洁明了，这就是写代码的最高境界，更是程序设计竞赛的精髓。

#include 
#include 
#include 
using namespace std;
vector<int> post, in;
map<int, int> level;
void pre(int root, int start, int end, int index) {
    if(start > end) return ;
    int i = start;
    while(i < end && in[i] != post[root]) i++;
    level[index] = post[root];
    pre(root - 1 - end + i, start, i - 1, 2 * index + 1);
    pre(root - 1, i + 1, end, 2 * index + 2);
}
int main() {
    int n;
    scanf("%d", &n);
    post.resize(n);
    in.resize(n);
    for(int i = 0; i < n; i++) scanf("%d", &post[i]);
    for(int i = 0; i < n; i++) scanf("%d", &in[i]);
    pre(n-1, 0, n-1, 0);
    auto it = level.begin();
    printf("%d", it->second);
    while(++it != level.end()) printf(" %d", it->second);
    return 0;
}

题型Ⅲ 已知先序中序求后序 分析

AC代码（引用自柳婼）

#include 
using namespace std;
int pre[] = {1, 2, 3, 4, 5, 6};
int in[] = {3, 2, 4, 1, 6, 5};
void post(int root, int start, int end) {
    if(start > end) 
        return ;
    int i = start;
    while(i < end && in[i] != pre[root]) i++;
    post(root + 1, start, i - 1);
    post(root + 1 + i - start, i + 1, end);
    printf("%d ", pre[root]);
}
 
int main() {
    post(0, 0, 5);
    return 0;
}

题型Ⅳ 已知先序中序求建二叉树

TreeNode* buildTree(int root, int start, int end) {
    if(start > end) return NULL;
    int i = start;
    while(i < end && in[i] != pre[root]) i++;
    TreeNode* t = new TreeNode();
    t->left = buildTree(root + 1, start, i - 1);
    t->right = buildTree(root + 1 + i - start, i + 1, end);
    t->data = pre[root];
    return t;
}

第二章 二叉树真题实战 Ⅰ 第二届天梯赛L2-2 树的遍历

题目链接

#include
using namespace std;
const int maxn=35;
int mid[maxn],pos[maxn],pre[maxn];
map<int,int> ans; 
void build(int root, int start, int end, int id){
    if(start>end)return;
    int i=start;
    while(i<end&&mid[i]!=pos[root])i++;
    ans[id]=pos[root];
    build(root-(end-(i-1)),start,i-1,id*2+1);
    build(root-1,i+1,end,id*2+2);
}
int main(){
    int N;cin>>N;
    for(int i=0;i<N;i++)cin>>pos[i];
    for(int i=0;i<N;i++)cin>>mid[i];
    build(N-1,0,N-1,0);
    auto i=ans.begin();
    for(i=ans.begin();i!=ans.end();i++){
        if(i!=ans.begin())cout<<" ";
        cout<<i->second;
    }
    cout<<endl;
    return 0;
}

Ⅱ 第七届天梯赛模拟L2-3 浪漫侧影

题目链接

#include
using namespace std;
const int maxn = 25;
int mid[maxn], pos[maxn], pre[maxn];
map<int, int> ans;
void build(int root, int start, int end, int id) {
	if (start>end)return;
	int i = start;
	while (i<end&&mid[i] != pos[root])i++;
	ans[id] = pos[root];
	build(root - (end - (i - 1)), start, i - 1, id * 2);
	build(root - 1, i + 1, end, id * 2 + 1);
}
int main() {
	int N; cin >> N;
	for (int i = 1; i <= N; i++)cin >> mid[i];
	for (int i = 1; i <= N; i++)cin >> pos[i];
	build(N, 1, N, 1);
	printf("R:");
	int now = 1;
	printf(" %d", ans[now]);
	for (int i = 1; i <= N; i++) {
		now *= 2;
		for (int j = now * 2 - 1; j >= now; j--) {
			if (ans[j]) {
				printf(" %d", ans[j]);
				break;
			}
		}
	}
	cout << endl;
	printf("L:");
	int cur = 1;
	printf(" %d", ans[cur]);
	for (int i = 1; i <= N; i++) {
		cur *= 2;
		for (int j = cur; j < cur * 2; j++) {
			if (ans[j]) {
				printf(" %d", ans[j]);
				break;
			}
		}
	}
	cout << endl;
	return 0;
}

Ⅲ 第三届天梯赛L2-3 玩转二叉树

题目链接

经典解法

直接建一颗二叉树。
复习一下：二叉树的先序中序后序遍历就是深度优先搜索，层序遍历就是广度优先搜索。
new可以代替malloc函数，为对象treenode分配内存空间。

#include
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 30 + 5;
int in[maxn], pre[maxn], post[maxn];
struct treenode{
	int data;
	treenode* left;
	treenode* right;
};
treenode* buildtree_inpost(int root, int start, int end) {
	if (start > end)return NULL;
	int i = start;
	while (i < end&&in[i] != post[root])i++;
	treenode* tree = new treenode();
	tree->left = buildtree_inpost(root - (end - (i - 1)), start, i - 1);
	tree->right = buildtree_inpost(root - 1, i + 1, end);
	tree->data = post[root];
	return tree;
}
treenode* buildtree_inpre(int root, int start, int end) {
	if (start > end)return NULL;
	int i = start;
	while (i < end&&in[i] != pre[root])i++;
	treenode* tree = new treenode();
	tree->left = buildtree_inpre(root + 1, start, i - 1);
	tree->right = buildtree_inpre(root + i - (start - 1), i + 1, end);
	tree->data = pre[root];
	return tree;
}
void pretravel(treenode* tree) {
	if (tree != NULL) {
		printf("%d ", tree->data);
		pretravel(tree->left);
		pretravel(tree->right);
	}
}
void intravel(treenode* tree) {
	if (tree != NULL) {
		intravel(tree->left);
		printf("%d ", tree->data);
		intravel(tree->right);
	}
}
void posttravel(treenode* tree) {
	if (tree != NULL) {
		posttravel(tree->left);
		posttravel(tree->right);
		printf("%d ", tree->data);
	}
}
void leveltravel(treenode* root) {
	queue<treenode*> q;
	q.push(root);
	while (!q.empty()) {
		treenode* tree = q.front();
		q.pop();
		if (tree->right != NULL)q.push(tree->right);
		if (tree->left != NULL)q.push(tree->left);
        printf("%d", tree->data);
        if(!q.empty())printf(" ");
	}
}
int main()
{
	int N; cin >> N;
	for (int i = 1; i <= N; i++)cin >> in[i];
	for (int i = 1; i <= N; i++)cin >> pre[i];
	treenode* root = buildtree_inpre(1, 1, N);
    /*
	printf("先序遍历结果为：");
	pretravel(root);
	cout << endl;
	printf("中序遍历结果为：");
	intravel(root);
	cout << endl;
	printf("后序遍历结果为：");
	posttravel(root);
	cout << endl;
	printf("层序遍历结果为：");
    */
	leveltravel(root);
	cout << endl;
    return 0;
}

简单解法

把层序遍历时原来左子树的编号和右子树的编号互换即可。

#include
using namespace std;
const int maxn=35;
int mid[maxn],pre[maxn],pos[maxn];
map<int,int> ans;
void build(int root, int start, int end, int id){
    if(start>end)return;
    int i=start;
    while(i<end&&mid[i]!=pre[root])i++;
    ans[id]=pre[root];
    build(root+1,start,i-1,id*2+1);
    build(root+i-(start-1),i+1,end,id*2);
}
int main(){
    int N;cin>>N;
    for(int i=1;i<=N;i++)cin>>mid[i];
    for(int i=1;i<=N;i++)cin>>pre[i];
    build(1,1,N,1);
    for(auto i=ans.begin();i!=ans.end();i++){
        if(i!=ans.begin())cout<<" ";
        cout<<i->second;
    }
    cout<<endl;
    return 0;
}

Ⅳ 第一届天梯赛L2-4 这是二叉搜索树吗？

题目链接

分析

这题坑的地方在于边界条件的判断。注意是 l e f t < = t a i l left<=tail left<=tail而不是 l e f t < t a i l leftleft<tail，因为假如 l e f t = = t a i l left==tail left==tail时条件成立，那么left的值会定格在 t a i l + 1 tail+1 tail+1，才可能使 l e f t − r i g h t = = 1 left-right==1 left−right==1成立。

AC代码

#include
using namespace std;
const int maxn=1e3+5;
int pre[maxn];
vector<int> post;
void build(int root, int tail, bool mirror){
    if(root>tail)return;
    int left=root+1,right=tail;
    if(mirror==false){
        while(pre[left]<pre[root]&&left<=tail)left++;
        while(pre[right]>=pre[root]&&right>root)right--;
    }
    else{
        while(pre[left]>=pre[root]&&left<=tail)left++;
        while(pre[right]<pre[root]&&right>root)right--;
    }
    if(left-right!=1)return;
    build(root+1,right,mirror);
    build(left,tail,mirror);
    post.push_back(pre[root]);
}
int main(){
    int N;cin>>N;
    for(int i=1;i<=N;i++)cin>>pre[i];
    bool ans=false;
    build(1,N,false);
    if(int(post.size())==N)ans=true;
    else{
        post.clear();
        build(1,N,true);
        if(int(post.size())==N)ans=true;
    }
    if(ans==false)puts("NO");
    else{
        puts("YES");
        for(auto i=post.begin();i!=post.end();i++){
            if(i!=post.begin())cout<<" ";
            cout<<*i;
        }
        cout<<endl;
    }
    return 0;
}

第三章 洛谷OJ二叉树专题集训 P4913 【深基16.例3】二叉树深度

题目描述
坑人的地方在于每一个父节点对应的子节点不是按照二叉树建立顺序连续输入的，因此不能直接在建立二叉树的同时输入子节点，而是应该先记录父子关系，再利用已知的父子关系建立二叉树。
当然直接深搜遍历亦可，这里用结构体指针建树只是为了练手，以应对更加复杂的情况。

#include
using namespace std;
const int maxn = 1e6 + 5;
int ans = 0, res = 0;
struct treenode {
	int data;
	treenode* left;
	treenode* right;
};
struct node {
	int l, r;
}son[maxn];
treenode* buildtree(int root) {
	treenode* tree = new treenode();
	if (son[root].l)tree->left = buildtree(son[root].l);
	if (son[root].r)tree->right = buildtree(son[root].r);
	tree->data = root;
	return tree;
}
void pretravel(treenode* root) {
	if (root == NULL)return;
	res++;
	ans = max(ans, res);
	pretravel(root->left);
	pretravel(root->right);
	res--;
}
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> son[i].l >> son[i].r;
	treenode* root = buildtree(1);
	pretravel(root);
	cout << ans << endl;
	return 0;
}

以上这些二叉树的基础题目应对天梯赛应该足够了。