上一篇文章我们讲了 BFS 的理论部分，现在来看一道例题。
例子
同样还是上一个例子
剑指Offer 55 - I
二叉树的深度
题目：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
给定二叉树[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回最大深度为 3 。
思路
直接按层序遍历，也即 BFS，记录下层深即可
那么怎么记录层深呢？
因为我们第一次是将根节点加入到了队列中，此时队列大小为 1，出队的时候我们只需遍历一次它的左孩子和右孩子，并将它们加入到队列中即可
那么如果当前队列中两个元素呢？
我们就必须遍历这两个节点的左右孩子，并将它们加入到队列当中
这样在加入完队列最后一个元素的左右孩子的时候，即将某一层的元素都加入到了当前队列中，此时深度 +1
我们只需在上述 BFS 遍历代码上稍加改造即可：
代码
publicintmaxDepth(TreeNoderoot) {
if (root==null) return0;
Queue<TreeNode>queue=newLinkedList<>();
queue.add(root);
intdepth=0; //初始时深度为0
while (!queue.isEmpty()) {
depth++;
intn=queue.size(); //获得队列当前的大小
for (inti=0; i<n; i++) { //出队并访问当前队列中所有元素
TreeNodenode=queue.poll(); //并将它们的左右孩子都加入到队列当中
if (node.left!=null) queue.add(node.left);
if (node.right!=null) queue.add(node.right);
}
}
returndepth;
}
