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

淘汰赛 P4715符合二叉树结构输入叶子结点。叶子结点共2^n 个则编号从2^n开始完美二叉树每层起始编号这层结点个数。for(inti0;i1n;i){// 一共2^n个结点cinv[(1n)i];// 树中编号从2^n开始往后1存国家的能力值ans[(1n)i]i1;// 国家编号1~2^n和i相差1}获胜的国家编号向上传递记录在父结点的ans值中。这个过程可以用递归来实现。// 主函数中从编号为1的结点开始dfs(1);voiddfs(intx){// 传入的是树结点的编号if(x1n)return;// 叶子结点if(v[x*2]v[x*21]){// 左儿子获胜v[x]v[x*2];// 获取能力值继续下一轮ans[x]ans[x*2];// 继承传递要的是初始国家的编号}else{// 右儿子胜利同理v[x]v[x*21];ans[x]ans[x*21];}}考虑输出求亚军是哪个国家最终是v[2]和v[3]进行比较获胜的是冠军另一个是亚军cout(v[2]v[3]?ans[2]:ans[3]);最后本道题开了两个数组一个是v数组记录国家能力值另一个是ans数组记录国家编号。那么数组要开多大呢结论层数为h的数由等比求和公式可知共有2^h - 1个结点。由题可知叶子结点有2n个说明树的高度hn1对着图简单推导一下。n最大是7那么树高h最大为8最多有28-1256-1个结点可取N260255。完整代码#includebits/stdc.husingnamespacestd;// h n 1// h 8// N 2^8-1 256-1constintN260;intv[N],ans[N];intn;voiddfs(intx){if(x1n)return;dfs(x*2);dfs(x*21);if(v[x*2]v[x*21]){v[x]v[x*2];ans[x]ans[x*2];}else{v[x]v[x*21];ans[x]ans[x*21];}}intmain(){cinn;for(inti0;i1n;i){cinv[(1n)i];ans[(1n)i]i1;}dfs(1);cout(v[2]v[3]?ans[2]:ans[3]);return0;}二叉树深度 P4913之前我们使用一维数组存储二叉树假设数深为h我们需要开一个2^h大小的数组空间复杂度太高。由于每个结点最多只有两个儿子所以可以对每个结点定义两个成员变量。递归返回结点x的深度。structNode{intleft,right;}a[N];输入树中结点编号注意从1开始存intn;cinn;for(inti1;in;i)// 这里用0会出问题因为题目中0代表空节点scanf(%d %d,a[i].left,a[i].right);递归函数// 主函数coutdfs(1);intdfs(intx){if(!x)return0;// 将叶子结点看作二叉树深度为0// 左右子树最大深度1returnmax(dfs(a[x].left),dfs(a[x].right))1;}完整代码#includebits/stdc.husingnamespacestd;constintN1000010;intn;structtree{intleft,right;}a[N];intdfs(intx){if(!x)return0;returnmax(dfs(a[x].left),dfs(a[x].right))1;}intmain(){cinn;for(inti1;in;i)scanf(%d %d,a[i].left,a[i].right);coutdfs(1);return0;}