华为练习 求二叉树的宽度和深度

那梓珊

　　求二叉树的宽度和深度

给定一个二叉树，获取该二叉树的宽度和深度。


例如输入

a

/ \

b c

/ \ / \

d e f g


返回3.

详细描述：


接口说明

原型：

int GetBiNodeInfo(BiNode &head, unsigned int *pulWidth, unsigned int *pulHeight)

输入参数：

head 需要获取深度的二叉树头结点

输出参数（指针指向的内存区域保证有效）：

pulWidth 宽度

pulHeight 高度

返回值：

0 成功

1 失败或其他异常

　　

　　

int DEEP;//深度，初始节点深度为0.则计算完了，将deep加一
int level[10010];//假定最高10010层。太大了就无法保存了。
//深度优先遍历
void DFS(int d,BiNode *n){//d为所要遍历的节点的层数
if(n != 0){
if(d > DEEP)
DEEP = d;
level[d] ++;
DFS(d+1,n->left);
DFS(d+1,n->right);
}
}
/*
Description  
给定一个二叉树，获取该二叉树的宽度深度。
Prototype
int GetBiNodeInfo(BiNode &head, unsigned int *pulWidth, unsigned int *pulHeight)
Input Param
head   需要获取深度的二叉树头结点
Output Param
pulWidth   宽度
pulHeight  高度
Return Value
0          成功
1          失败或其他异常
*/
int GetBiNodeInfo(BiNode &head, unsigned int *pulWidth, unsigned int *pulHeight)
{
/*在这里实现功能*/
for(int i = 0; i < 10010;i++)
level = 0;
DEEP = 0;
DFS(0,&head);
DEEP++;
*pulHeight = DEEP;
DEEP = 0;
for(int i =0; i < 10010;i++)
DEEP = level > DEEP ? level : DEEP;
*pulWidth = DEEP;
return 0;
}