题目选自洛谷P4715

二叉树知识点入门题目，便于学习、熟悉二叉树这种数据结构以及解题方法

用value[]和win[]分别来记录能力值和国家编号，

叶子层就是输入的能力值和国家编号，

对二叉树进行dfs，结束条件为叶子结点，

分别计算左右子树的结点值，并将获胜的编号、能力值保存到对应的父结点中，

最后比较二叉树2、3编号的能力值大小即可。

 

题目描述

有 2^n(n≤7) 个国家参加世界杯决赛圈且进入淘汰赛环节。我经知道各个国家的能力值，且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛，胜者晋级。3 号国家和 4 号国家也踢一场，胜者晋级……晋级后的国家用相同的方法继续完成赛程，直到决出冠军。给出各个国家的能力值，请问亚军是哪个国家？

输入格式

无

输出格式

无

输入输出样例

输入 1

3
4 2 3 1 10 5 9 7

输出 1

1

解题代码：
 

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
int value[260],win[260]; //value保存能力值，win记录国家编号
int n;
void dfs(int x){
	if(x >= 1<<n) //叶子结点直接返回
		return;
	else{
		dfs(2 * x); //左子树
		dfs(2 * x + 1); //右子树
		//走到这里后，代表已经到最底层了，可以计算了
		int lvalue = value[2 * x], rvalue = value[2 * x + 1];
		if(lvalue > rvalue){ //如果左边赢了
			win[x] = win[2 * x];
			value[x] = lvalue;
		}else{
			win[x] = win[2 * x + 1];
			value[x] = rvalue;
		}
	}
}
int main(){
	cin>>n;
	//保存数据到叶子结点
	for(int i=0;i< (1<<n);i++){
		cin>>value[i + (1<<n)]; //value叶子结点就是对应的能力值
		win[i + (1<<n)] = i + 1; //叶子结点首先是存放国家
	}
	dfs(1); //从根结点开始遍历
	cout<<((value[2]>value[3])?(win[3]):(win[2]));
	return 0;
}