求树的最大宽度

所谓二叉树的宽度是指：二叉树各层节点个数的最大值。
我们知道层序遍历二叉树是使用deque来实现的：每次打印一个节点之后，如果存在左右子树，则把左右子树压入deque，那么此时的队列中可能既包含当前层的节点，也包含下一层的节点。

而我们要求的是对于特定某一层的节点的个数，因此我们需要从头结点开始，记录每一层的个数，对于当前层的每一个节点，在弹出自身之后把其左右子树压入deque，当把当前层全部弹出队列之后，在队列中剩下的就是下一层的节点。然后比较队列的size和之前得到的maxWidth，取最大值即为队列的宽度。最终队列为空，得到的maxWidth就是二叉树的宽度！

/* 二叉树的宽度      在上一层遍历完成后，下一层的所有节点已经放到队列中，此时队列中的元素个数就是下一层的宽度*/
/************************************************************************/
int WidthOfBinaryTree(BinaryTreeNode*pNode){
    if (pNode == NULL)
    {
        return 0;
    }
    std::deque<BinaryTreeNode*> dequeTreeNode;//双端队列
    int maxWidth = 1;//最大的宽度,用于当只有一个节点时候返回1
    dequeTreeNode.push_back(pNode);//头结点入队
    while (true)
    {

        int length = dequeTreeNode.size();//当前层节点的个数
        if (length == 0)//当前层没有节点，跳出循环
        {
            break;
        }
        while (length > 0)//如果当前层还有节点
        {
            BinaryTreeNode* pTemp = dequeTreeNode.front();
            dequeTreeNode.pop_front();//出队
            length--;//长度减一
            if (pTemp->m_pLeft)
            {
                dequeTreeNode.push_back(pTemp->m_pLeft);//下一层节点入队
            }
            if (pTemp->m_pRight)
            {
                dequeTreeNode.push_back(pTemp->m_pRight);//下一层节点入队
            }
        }
        maxWidth = maxWidth > dequeTreeNode.size() ? maxWidth : dequeTreeNode.size();//得到最大宽度
    }
    return maxWidth;
}

二叉树系列——二叉树的宽度