步骤1、实现BFS广度优先遍历
void BFS(Node root){
Queue<Node> queue = new LinkedList<>(); //创建队列,使用链表实现队列接口(同时队列接口继承了collection接口)
queue.add(root); //root进入队列
while(!queue.isEmpty()){ //如果队列不为空
Node ptr = queue.poll(); //循环删除并获取队首元素
System.out.println(ptr.value); //打印队首元素的值
if(ptr.left != null){ //左子节点不为空
queue.add(ptr.left); //队列添加左子节点
}
if(ptr.right != null){ //右子节点不为空
queue.add(ptr.right); //添加右子节点
}
}
}
此时可以逐层打印所有元素,但是无法区分每个元素具体来自哪一层(ps:只知道有多少个节点,无法统计二叉树的最大深度)
步骤2、实现层序遍历
int currentLevelNodes = queue.size(); //拿到当前队列长度(第n层共有多少个元素)
for (int i = 0; i < currentLevelNodes; i++) { //循环
Node ptr = queue.poll(); //访问当前队列所有元素(访问第n层的每个元素)
...
}
将步骤1和上面的代码合并起来
void BFSplus(Node root){
Queue<Node> queue = new LinkedList<>();
queue.add(root);
int level = 0;
String mark = "-- ";
while(!queue.isEmpty()){
int currentLevelNodes = queue.size();
level++;
for (int i = 0; i < currentLevelNodes; i++) {
Node ptr = queue.poll();
System.out.println(
level + "st level " + mark + ptr.value);
if(ptr.left!=null)
queue.add(ptr.left);
if(ptr.right!=null)
queue.add(ptr.right);
}
mark += mark;
System.out.println();
}
}
打印结果
1st level -- 1
2st level -- -- 2
2st level -- -- 3
3st level -- -- -- -- 4
3st level -- -- -- -- 5
...
将level返回即可得到二叉树的最大深度
回到原题(将Node变为TreeNode)
public int maxDepth (TreeNode root) {
if(root == null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 0;
while(!queue.isEmpty()){
int n = queue.size();
level++; //在外循环和内循环中间添加level统计层数
for (int i = 0; i < n; i++) {
TreeNode node = queue.poll();
if(node.left!=null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
}
return level;
}