深入浅出 16.1 例题（二叉树）P4715 P4913

淘汰赛 P4715

符合二叉树结构

输入叶子结点。叶子结点共2^n 个，则编号从2^n开始（完美二叉树每层起始编号=这层结点个数）。

for(inti=0;i<1<<n;i++){// 一共2^n个结点cin>>v[(1<<n)+i];// 树中编号从2^n开始，往后+1，存国家的能力值ans[(1<<n)+i]=i+1;// 国家编号1~2^n，和i相差1}

获胜的国家编号向上传递，记录在父结点的ans值中。
这个过程可以用递归来实现。

// 主函数中从编号为1的结点开始dfs(1);voiddfs(intx){// 传入的是树结点的编号if(x>=1<<n)return;// 叶子结点if(v[x*2]>v[x*2+1]){// 左儿子获胜v[x]=v[x*2];// 获取能力值，继续下一轮ans[x]=ans[x*2];// 继承传递，要的是初始国家的编号}else{// 右儿子胜利，同理v[x]=v[x*2+1];ans[x]=ans[x*2+1];}}

考虑输出
求亚军是哪个国家，最终是v[2]和v[3]进行比较，获胜的是冠军，另一个是亚军

cout<<(v[2]<v[3]?ans[2]:ans[3]);

最后，本道题开了两个数组，一个是v数组，记录国家能力值；另一个是ans数组，记录国家编号。那么数组要开多大呢？
结论：层数为h的数（由等比求和公式可知）共有2^h - 1个结点。
由题可知，叶子结点有2^{n个，说明树的高度h=n+1（对着图简单推导一下）。n最大是7，那么树高h最大为8，最多有2}8-1=256-1个结点，可取N=260（>=255）。

完整代码

#include<bits/stdc++.h>usingnamespacestd;// h = n + 1// h = 8// N = 2^8-1 = 256-1constintN=260;intv[N],ans[N];intn;voiddfs(intx){if(x>=1<<n)return;dfs(x*2);dfs(x*2+1);if(v[x*2]>v[x*2+1]){v[x]=v[x*2];ans[x]=ans[x*2];}else{v[x]=v[x*2+1];ans[x]=ans[x*2+1];}}intmain(){cin>>n;for(inti=0;i<1<<n;i++){cin>>v[(1<<n)+i];ans[(1<<n)+i]=i+1;}dfs(1);cout<<(v[2]<v[3]?ans[2]:ans[3]);return0;}

二叉树深度 P4913

之前我们使用一维数组存储二叉树，假设数深为h，我们需要开一个2^h大小的数组，空间复杂度太高。
由于每个结点最多只有两个儿子，所以可以对每个结点定义两个成员变量。
递归返回结点x的深度。

structNode{intleft,right;}a[N];

输入（树中结点编号注意从1开始存）

intn;cin>>n;for(inti=1;i<=n;i++)// 这里用0会出问题，因为题目中0代表空节点scanf("%d %d",&a[i].left,&a[i].right);

递归函数

// 主函数cout<<dfs(1);intdfs(intx){if(!x)return0;// 将叶子结点看作二叉树，深度为0// 左右子树最大深度+1returnmax(dfs(a[x].left),dfs(a[x].right))+1;}

完整代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1000010;intn;structtree{intleft,right;}a[N];intdfs(intx){if(!x)return0;returnmax(dfs(a[x].left),dfs(a[x].right))+1;}intmain(){cin>>n;for(inti=1;i<=n;i++)scanf("%d %d",&a[i].left,&a[i].right);cout<<dfs(1);return0;}