求二叉树的宽度和深度
给定一个二叉树,获取该二叉树的宽度和深度。
例如输入
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[i] = 0; DEEP = 0; DFS(0,&head); DEEP++; *pulHeight = DEEP; DEEP = 0; for(int i =0; i < 10010;i++) DEEP = level[i] > DEEP ? level[i] : DEEP; *pulWidth = DEEP; return 0; }