题解 | #Java BFS和层序遍历求二叉树的最大深度#

步骤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;
    }