输入理解：按先序遍历排列，#表示空
思路算法；模拟，同时不断更新深度和宽度，如果某一个节点没有左右孩子节点，那么他就是一个子节点，具体详见程序
本程序关键变量含义：
k表示当前的层数，t表示当前节点的父亲节点的编号，x=1表示这是左孩子节点，x=2表示这是右孩子节点
n表示节点个数，因为n随时变动，所以设置一个nn表示这个节点的编号
p表示当前正在扫描s的第p个字符
a[n]表示第n个节点的编号（基本可以无视，因为a[n]=n）
c[k]表示第k层节点的个数（与宽度有关）
b[t,1]表示第t个节点的左孩子节点的编号，b[t,2]表示第t个节点的右孩子节点的编号
maxh表示最大的深度，maxw表示最大的宽度，及题目中的该二叉树的深度和宽度
参考程序：var
a,c:array[0..100000] of longint;
b:array[0..100000,1..2] of longint;
p,n,i,ans,maxw,maxh:longint;
s:ansistring;
procedure init(k,t,x:longint);
var
nn:longint;
begin
p:=p+1;//扫描下一个字符
if s[p]='#' then exit else//如果是#，那么就回到上一层
begin
n:=n+1;//节点数加一
a[n]:=n;
b[t,x]:=n;//父亲节点的子节点编号进行统计
c[k]:=c[k]+1;//当前高度节点的个数+1，即k高度的宽度+1
if c[k]>maxw then maxw:=c[k];
if k>maxh then maxh:=k;//刷新数的深度和高度
nn:=n;//保存当前节点的编号，避免n的变动引起误差
init(k+1,nn,1);//递归到左孩子节点
init(k+1,nn,2);//递归到右孩子节点
end;
end;
begin
readln(s);
init(1,0,1);//为了方便起见，设置1号节点为0号节点的左孩子节点，对结果无影响
for i:=1 to n do
if (b[i,1]=0) and (b[i,2]=0) then ans:=ans+1;//扫描，如果左孩子和右孩子节点都不存在（即=0），那么子节点个数+1
writeln(ans);
writeln(maxh,' ',maxw);//输出结果
end.
经测试，本程序可以通过样例数据
若还是不理解，可以尝试数据跟踪进行调试
若还是不理解，欢迎追问。
若觉得好，请采纳！ |
转播
