4511: 【例】【入门】求二叉树的深度及遍历结果(2183)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
从键盘读入一棵二叉树，请问这棵二叉树的深度是多少？这棵二叉树如果后序遍历的结果是什么？
输入
第 行输入一个整数 ，代表读入的数据数量。（）
第 行读入 个非负整数，代表读入的数据，读入的整数中，如果值大于 ，代表的是二叉树的结点，如果值等于 ，代表当前结点为空。（根结点的深度为 ）
二叉树的构造按照层次顺序（即第 层 个整数，第 层 个，第 层 个，第 层有 个，如果某个结点不存在以 代替）。
样例数据确保读入的第 个整数 。
输出
输出有 行；
第 行输出该二叉树的深度；
第 行输出后序遍历二叉树得到的序列，数字之间用空格隔开；
样例输入 复制
5
1 2 0 3 4样例输出 复制
3
3 4 2 1提示
【样例解释】
样例对应二叉树如下图所示：
#include<bits/stdc++.h>
using namespace std;
/*
用数组读入二叉树
i号结点的左孩子一定是：2*i
i号结点的右孩子一定是：2*i+1
*/
const int N=110;
int a[N];
int n;
//后序遍历
void dfs(int x) {
if (x*2<=n&&a[x*2]) dfs(x*2);
if (x*2+1<=n&&a[x*2+1]) dfs(x*2+1);
cout<<a[x]<<" "; //左右根
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
}
//int(log2(n)) + 1
cout<<(int)log2(n) + 1<<endl;
dfs(1); //从下标（编号）为1的点开始深搜
return 0;
}