codevs刷题日记·白银
先声明一下本蒟蒻现在的等级>_< （没错，才白银）
第一篇codevs刷题日记！！！（写的不好见谅）
白银还是比较简单的(立个flag)，这次先写个递归框的题
1501 二叉树最大宽度和高度
http://codevs.cn/problem/1501/
给出一个二叉树，输出它的最大宽度和高度。 输入： 第一行一个整数n。 下面n行每行有两个数，对于第i行的两个数，代表编号为i的节点所连接>的两个左右儿子的编号。如果没有某个儿子为空，则为0。 输出： 输出共一行，输出二叉树的最大宽度和高度，用一个空格隔开。
思考过程:
看到数据里面n<16+递归,秒选搜索 但是这个作者十分诡异 这道题除了搜索还能干吗?动态规划? 不过这作者还挺好，给了一个边界点 直接先写一个1 0 0判定，是的直接输出 总体先建一个二叉树，再读入，深度用深搜，宽度用宽搜，O(2*2^15)可以通过
不对不对！！！
深度可以直接通过一层层迭代：读入左右儿子时直接给左右儿子的depth赋值，再单独更新n-1次depth,打擂台法取最大(这里不直接赋值是避免故意写一个3 0 0 0 0 1 2之类的数据（序号大的反而在上面的），复杂度为O(2n)(朴素的方法)
宽度也用打擂台，不同的是取每一行的前一行的总孩子数，这个可以预选用O(n)算好，然后再比较，复杂度为O(n)
还有一件事：1 0 0
大功告成！ 附上AC代码：
#include< bits/stdc++.h>
using namespace std; struct node { int left,right;//左右儿子 int child;//记录宽度用 int father,depth;//father为0则是根 }; node t[20]; int n,width[20]={0}; int main() { cin>>n; t[1].depth=1; t[1].father=1;//预先处理根 for(int i=1;i<=n;i++) { scanf(“%d %d”,&t[i].left,&t[i].right); if(n==1&&t[i].left==0&&t[i].right==0)//特殊判定 { printf(“1 1”); return 0; } if(t[i].left!=0)//有无点 { t[t[i].left].father=i;//t[i]的左右儿子的父亲节点肯定是t[i] t[i].child++; } if(t[i].right!=0) { t[t[i].right].father=i; t[i].child++; } } for(int i=1;i<=3;i++)//防止极端这种数据 { for(int j=2;j<=n;j++)//防止退化成链表 { t[j].depth=t[t[j].father].depth+1;//更新深度 } } for(int i=1;i<=n;i++) { width[t[i].depth]+=t[i].child;//以深度为下标 } int maxw=0,maxd=0; for(int i=1;i<=n;i++)//打擂台 { maxd=max(maxd,t[i].depth); maxw=max(maxw,width[i]); } printf(“%d %d”,maxw,maxd); } AC证明：
