** 二叉树的层序遍历 * * '1' * | | * '2' '3' * | | | | * 4 '5' 6 7' * | | | * 8 '9 '11 * | | * 10 12 * ' 代表是否有左右节点 * * 二叉树宽度优先遍历首要原则: 如何保证这一层遍历完了!!! *
方式一:
//方式一: 求树的最大宽度 仅使用队列实现
public static int maxBFS(Node node){
int max = -1;
Queue queue = new linkedList<>();
queue.add(node);
Node curEnd = node;
Node nextEnd = null;
int curLevelNodes = 0;
while (!queue.isEmpty()){
node = queue.poll();
if(node.left != null){
queue.add(node.left);
nextEnd = node.left;
}
if(node.right != null){
queue.add(node.right);
nextEnd = node.right;
}
curLevelNodes ++;
if(node == curEnd){
if(curLevelNodes > max){
max = curLevelNodes;
}
curEnd = nextEnd;
curLevelNodes = 0;
}
}
return max;
}
方式二:
//方式二: 求树的最大宽度 借助map实现
public static int maxBroadOfTree(Node node){
int max = -1;
int level = 1; //初始处于第1层
int curLevelNodes = 0; //当前层统计的节点数
Queue queue = new linkedList<>();
HashMap levelMap = new HashMap<>(); //确保自己遍历到哪一层了
levelMap.put(node,1);
queue.add(node);
//BFS需要统计每层的节点数,然后决出最大宽度
while (!queue.isEmpty()){
Node cur = queue.poll();
if(cur.left != null){
queue.add(cur.left);
//只要有新节点产生,在levelMap中记录"层",后续备用
levelMap.put(cur.left,levelMap.get(cur) + 1);
}
if(cur.right != null){
queue.add(cur.right);
levelMap.put(cur.right,levelMap.get(cur) + 1);
}
//最后一层统计完但不会再有下层level触发此条件,所以curLevelNodes没有更新到max
if(level == levelMap.get(cur)){
curLevelNodes ++;
}else{
if(curLevelNodes > max){
max = curLevelNodes;
}
//+1 是因为由于弹出的节点已经是下一层的了,所以先 +1
curLevelNodes = 1;
level ++;
}
}
//当队列弹空后,统计工作已完成,但未完成更新
if(curLevelNodes > max){
max = curLevelNodes;
}
return max;
}
左神算法学习
