一、二叉树的宽度
二叉树的宽度是指含有最多节点数的对应层对应的节点数，我们之前提到了二叉树的层次遍历，二叉树的宽度其实也是基于层次遍历实现的。
我们只需要在每一次记录队列的长度，每一次出队列出去的是当前这一层的全部结点，这样即可通过对比每一层的长度来实现获取最大宽度
二、二叉树的宽度代码实现
public static int maxWidth(BTNode node) {
int maxWidth = 1, width;
ArrayDeque<BTNode> queue = new ArrayDeque<>();
//根节点入队
queue.add(node);
while (!queue.isEmpty()) {
width = queue.size();
//若每一层的宽度大于maxWidth，则重新赋值
maxWidth = maxWidth < width ? width :maxWidth;
//注意这里循环的次数是width,出队的仅仅是每一层的元素
for (int i = 0; i < width; i++) {
BTNode nodeTemp = queue.poll();
if (nodeTemp.leftChild != null) {
queue.add(nodeTemp.leftChild);
}
if(nodeTemp.rightChild != null) {
queue.add(nodeTemp.rightChild);
}
}
}
return maxWidth;
}
三、测试代码
/**
* 构建二叉树
* 3
* 2 4
* 5 2 2 4
* 5
*
* @param args
*/
public static void main(String[] args) {
int[] a = {3, 2, 4, 5, 2, 2, 4, 5};
BTNode root = BTNodeUtil.createBTNodebyArray(a);
System.out.print("该二叉树的最大宽度为：" + maxWidth(root));
}
输出
该二叉树的最大宽度为：4
