题目： 给定一颗二叉树，求二叉树的宽度。
宽度的定义： 二叉树的宽度定义为具有最多结点数的层中包含的结点数。
比如上图中，第 1 层有 1 个结点， 第 2 层有 2 个结点， 第 3 层有 4 个结点， 第 4 层有 1 个结点。可知，第 3 层的结点数最多，所以这棵二叉树的宽度是 4。
求解思路： 这里需要用到二叉树的层次遍历，即广度优先周游。在层次遍历的过程中，通过读取队列中保留的上一层的结点数来记录每层的结点数，以获取所有层中最大的结点数。关于二叉树广度优先周游，参考：二叉树的遍历。
具体实现：
代码语言：javascript复制//求二叉树的宽度
int treeWidth(BinaryTreeNode *pRoot) {
if (pRoot == NULL) return 0;
queue<BinaryTreeNode*> myQueue;
myQueue.push(pRoot); // 将根结点入队列
int nWidth = 1; // 二叉树的宽度
int nCurLevelWidth = 1; // 记录当前层的宽度
BinaryTreeNode *pCur = NULL;
// 队列不为空
while (!myQueue.empty()) {
while (nCurLevelWidth != 0) {
pCur = myQueue.front(); // 取出队首元素
myQueue.pop(); // 队首元素出队列
if (pCur->m_pLeft != NULL) myQueue.push(pCur->m_pLeft);
if (pCur->m_pRight != NULL) myQueue.push(pCur->m_pRight);
nCurLevelWidth--;
}
nCurLevelWidth = myQueue.size();
nWidth = nCurLevelWidth > nWidth ? nCurLevelWidth : nWidth;
}
return nWidth;
}参考文献
[1] 何海涛.剑指Offer[M].电子工业出版社. [2] CSDN.求二叉树的深度和宽度
