[华为机试练习题]42.求二叉树的深度和宽度

题目

题目标题：

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

例如输入
   a
  / \
 b   c
/ \ / \
d e f g

返回3.

接口说明
原型：

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

输入参数：

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

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

     pulWidth   宽度
     pulHeight  高度

返回值：

     0          成功
     1          失败或其他异常

练习阶段:

中级 

代码

/*---------------------------------------
*   日期：2015-07-03
*   作者：SJF0115
*   题目：求二叉树的深度和宽度
*   来源：华为机试练习题
-----------------------------------------*/
#include <iostream>
#include "OJ.h"
#include <string>
#include <queue>
using namespace std;

/*
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){
    if(&head == NULL || pulWidth == NULL || pulHeight == NULL){
        return 1;
    }//if
    int maxWidth = 0;
    int curWidth = 0;
    int height = 0;
    BiNode* root = &head;
    queue<BiNode*> curQueue;
    queue<BiNode*> nextQueue;
    curQueue.push(root);
    // 层次遍历
    while(!curQueue.empty()){
        ++height;
        curWidth = 0;
        while(!curQueue.empty()){
            ++curWidth;
            BiNode* node = curQueue.front();
            curQueue.pop();
            // 左子结点不为空
            if(node->left != NULL){
                nextQueue.push(node->left);
            }//if
            // 右子节点不为空
            if(node->right != NULL){
                nextQueue.push(node->right);
            }//if
        }//while
        // 更新最大宽度
        if(curWidth > maxWidth){
            maxWidth = curWidth;
        }//if
        swap(curQueue,nextQueue);
    }//while
    *pulWidth = maxWidth;
    *pulHeight = height;
    return 0;
}

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>