提示：这是互联网大厂的经典面试题！
重要基础知识：
自然，按层遍历，基础代码就是二叉树的BFS！
（1）二叉树的宽度优先遍历BFS：按层的遍历方式，请你用队列实现DFS，或者请你用栈实现BFS
文章目录
- 经典面试题：请你统计二叉树的最大宽度，即某一层节点数目最大值
- @[TOC](文章目录)
- 题目
- 一、审题
- 二、笔试求AC，不考虑空间复杂度
- 三、面试求最优解，空间复杂度为o(1)
- 总结
给你一颗二叉树，其头节点为head，请你统计二叉树的最大宽度，即统计二叉树的某一层中，节点数目的最大值
一、审题
示例：下图中，低3层的节点数最多，4个，返回max=4
把问题的节点和二叉树
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int v){
value = v;
}
}
//构造一颗树，今后方便使用
public static Node generateBinaryTree(){
//树长啥样呢
// 1
// 2 3
// 4 5 6 7
// 8 9
Node head = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
head.left = n2;
head.right = n3;
Node n4 = new Node(4);
Node n5 = new Node(5);
n2.left = n4;
n2.right = n5;
Node n6 = new Node(6);
Node n7 = new Node(7);
n3.left = n6;
n3.right = n7;
Node n8 = new Node(8);
Node n9 = new Node(9);
n5.left = n8;
n6.right = n9;
return head;
}
二、笔试求AC，不考虑空间复杂度
其实，二叉树，和链表本质是一个东西，只是摆法不一样
在链表中，我们说过了，但凡给你一个题，求啥，你都得遍历所有的节点，故o(n)的时间复杂度你摆脱不了
那么我们说能优化的往往就是空间了
简单的代码，肯定可以通过外部申请额外空间来搞定，思想简单，但是必然耗费空间。这不是最优解，却是通过笔试的好方法。
如何统计二叉树的一层中有多少个节点？
那么你需要知道什么时候遍历一层的第一个节点？
什么时候遍历一层的最后一个节点？
这样你才能统计这一层的节点个数。
自然，按层遍历，基础代码就是二叉树的BFS！
（1）二叉树的宽度优先遍历BFS：按层的遍历方式，请你用队列实现DFS，或者请你用栈实现BFS
如果我们知道啥时候一层开始了，啥时候一层结束了？
OK，开始到结束，我们统计当前层的节点个数，完事了呗！！
那么宏观调度就是：每一个层，统计一下这一层的节点个数，然后全程我们用max更新最大值，最后一层遍历统计完就能得到结果。
如何实现这个机制呢？
笔试AC的耗费空间方法
我们用哈希表来存每一个节点cur，它所在的层，比如map：
head在第1层
1和3在第2层
4567在第3层
OK，我们来控制知道啥时候新的一层开始了，啥时候这一层统计结束了？核心思想就是：
（1）我们玩BFS，首次遇到head，自然，初始化其层数（curLevel）是1，当前层节点数（curLevelNodes=1）
（2）遍历cur=2时，我们显然发现当前层curLevel=map.get(2节点）=2了，不再是1，说明新的一层开始了，咱就需要清算上一层节点数最大值，更新给max，max=1；
（3）初始化当前层节点数（curLevelNodes=1），curLevel=2，遍历到cur=3时，前层curLevel=map.get(3节点）=2，它等于curLevel=2，说明，我们确实在统计第2层，那么curLevelNodes++=2，
（4）遍历到cur=4时，前层curLevel=map.get(4节点）=3，它不等于curLevel=2，说明第2层统计已经完成，咱需要清算第2层的节点数，把max更新好，max=2；
（5）初始化当前层节点数（curLevelNodes=1），curLevel=3，说明我们开始统计第3层的节点数了……
——依次循环这么玩BFS，途中，别忘了cur的左右子依次按照BFS进队列。与此同时，将他们的层数加入map中，自然cur的左右子，他们的层数，是curLevel+1，这是自然的。
（6）直到最后一层搞定统计，更新给max，返回结果即可。
就通过上面这种，遍历的节点，它的层数突变时，来知晓上一层统计已经结束，清算更新max
然后初始化新的一层开始了。！！！
明白了吧？
手撕代码：【懂了核心思想，手撕代码不是问题！！！】
//复习：遍历的节点，它的层数突变时，来知晓上一层统计已经结束，清算更新max
//然后初始化新的一层开始了。！！！
public static int btMaxBreadth(Node head){
if (head == null) return 0;
//哈希表统计每个点的层数，BFS住宏观调度
HashMap<Node, Integer> map = new HashMap();
map.put(head, 1);//第一层
LinkedList<Node> queue = new LinkedList<>();
queue.add(head);//完成BFS的过程
int max = 1;//起码头节点是1个
int curLevel = 1;//从第一层开始玩
int curLevelNodes = 0;//暂时还没有统计到
while (!queue.isEmpty()){
Node cur = queue.poll();
//System.out.print(cur.value + " ");
int curNodeLevel = map.get(cur);//来一个cur就拿一波它所在的层数
//按层加入左右子-并记录每个点的层，这是必须要做得宏观调度
if (cur.left != null) {
queue.add(cur.left);
map.put(cur.left, curLevel + 1);
}
if (cur.right != null) {
queue.add(cur.right);
map.put(cur.right, curLevel + 1);
}
//然后就要开始对比清算，当前节点是不是已经到了新的一层了呢？
if (curNodeLevel == curLevel){
//相等，就继续统计
curLevelNodes++;
}else {
//curNodeLevel != curLevel,这是就意味着上一层结束，新的一层开始了，清算max
max = Math.max(max, curLevelNodes);
curLevel++;//新的一层开始
curLevelNodes = 1;//暂时cur算第一个
}
}
//BFS走完后，队列为空，但是最后一层还没有更新
max = Math.max(max, curLevelNodes);
return max;
}
public static void test2(){
Node head = generateBinaryTree();
int max = btMaxBreadth(head);
System.out.println(max);
}
public static void main(String[] args) {
// test();
test2();
}
结果：4
说白了，就是要判断当碰到的cur节点，它所在的层curNodeLevel，是不是等于我们一直统计的层curLevel，一旦突变，就说明去新的一层开始了，要先清算max。
很简单吧！
面试也类似，只不过，咱们不要哈希表来存每个节点的层数了。
那我们咋才能知道，每一次统计到一层最后一个节点了呢？
（1）你观察一下，头节点，是不是就是第一层的最后一个节点curEnd？
是的
（2）那么我问你，是不是头节点的右子head.right，它就是第二层的最后一个节点？
是的，而且咱现在说的头节点，就是当前层最后一个节点
——也就是说，每一层最后一个节点curEnd，它的右子，curEnd.right就是下一层的最后一个节点？
咱们令下一层的最后一个节点是nextEnd。
这是不是很容易理解！
【当然，实际可能没有右子，那就是左子是当前层最后一个节点，没关系的。】
好了，你当前层最后一个节点curEnd知道了，你从左边开始，每次统计当前层的节点数curLevelNodes++，一旦遇到curEnd
是不是该清算max了
然后你初始化：curEnd=nextEnd。接下来你统计下一层的时候，是不是就很轻松知道：啥时候停止了？
宏观调度已然是BFS，遇到cur，其左右子不空压入队列，同时，看看cur是不是curEnd，是就将其右子赋值给nextEnd。
看下图：
我们当前统计的是2层，目前从左到右已经有n=2个了，cur恰好来到curEnd，那需要清算max=2
现在，让nextEnd=nextEnd.right，令curEnd=nextEnd=7节点，n=0；
因为你马上要去统计下第三层了，所以curEnd就是要更新为第三层那个nextEnd
就是这样的控制方法，让我们清楚知道啥时候一层统计完成。更新max！
这就是不用耗费额外空间的最优解！！！
懂了思想，自然手撕代码不是问题：
//面试代码：你当前层最后一个节点curEnd知道了，你从左边开始，每次统计当前层的节点数curLevelNodes++，一旦遇到curEnd
//清算max了
//然后你初始化：nextEnd = nextEnd.right, curEnd=nextEnd。curLevelNodes=0
// 接下来你统计下一层的时候，是不是就很轻松知道：啥时候停止了？
//宏观调度已然是BFS，遇到cur，其左右子不空压入队列，同时，看看cur是不是curEnd，是就将其右子赋值给nextEnd。
public static int btMaxBreadthFace(Node head){
if (head == null) return 0;
//不用哈希表
//BFS依然是宏观调度
LinkedList<Node> queue = new LinkedList<>();
queue.add(head);
//初始化curEnd和nextEnd
Node curEnd = head;
Node nextEnd = null;
int curLevelNodes = 0;//统计当前层节点数量
int max = 1;//至少为1
while (!queue.isEmpty()){
Node cur = queue.poll();
//System.out.print(cur.value + " ");
curLevelNodes++;//遇到就要统计
//按层加入左右子
if (cur.left != null) {
queue.add(cur.left);
//每次都要检查cur是否为curEnd
if (cur == curEnd) nextEnd = cur.left;
}
if (cur.right != null) {
queue.add(cur.right);
//每次都要检查cur是否为curEnd
if (cur == curEnd) nextEnd = cur.right;
}
//检查是否到了最后一个节点
if (cur == curEnd){
//cur == curEnd清算max，初始化新的一层参数
max = Math.max(max, curLevelNodes);
curLevelNodes = 0;
curEnd = nextEnd;
}
}
return max;
}
public static void test2(){
Node head = generateBinaryTree();
int max = btMaxBreadth(head);
System.out.println(max);
int max2 = btMaxBreadthFace(head);
System.out.println(max2);
}
public static void main(String[] args) {
// test();
test2();
}
但凡遇到一个cur，就要统计当前层节点数量++；
但凡cur是curEnd，就要清算
核心思想很简单，其实这代码比笔试那个哈希表的代码好写。
结果测试：
4
4
总结
提示：重要经验：
1）统计二叉树的最大宽度，最后其实面试最优解的代码，比笔试AC那个代码要好写，但是核心思想都一样。
2）本题核心思想关键在知晓每一层最后一个节点那清算max，然后下一层一切从头开始。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）