Width of Binary Trees

题目描述
The maximum number of nodes in all levels in a binary tree is called the width of the tree. For example, the binary tree on the right in the following figure has width 4 because the maximum number of nodes is 4 on the third level.

The treeNode is defined as follows.

typedef int T;
struct treeNode {
T data;
struct treeNode *left, *right;
treeNode(T d, treeNode *l=NULL, treeNode *r=NULL):data(d),left(l),right(r){};
};

Implement the following function that computes the width of a binary tree.

int width(const treeNode * root);
// return the width of the binary tree root.

参考答案

#include <iostream>
#include "width.h"
#include <queue>
using namespace std;

int width(const treeNode *root)
{
    if (root == NULL)
        return 0;
    int max = 1;
    queue<const treeNode *> q;
    q.push(root);
    while (1)
    {
        int len = q.size();
        if (len == 0)
            break;
        while (len > 0)
        {
            const treeNode * tmp = q.front();
            q.pop();
            --len;
            if (tmp->left)
                q.push(tmp->left);
            if (tmp->right)
                q.push(tmp->right);
        }
        max = (q.size() > max) ? q.size() : max;
    }
    return max;
}