二叉树的遍历问题—广度优先实现(从代码理解算法)

问题的引入

本文主要对二叉树的广度优先搜索代码实现做一个梳理，加深自己对算法的理解，也供大家参考学习。

我们以最大路径问题为例来说明二叉树的广度优先遍历的实现。

LeetCode 104. 二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。

二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

LeetCode104

二叉树的广度优先遍历的解释

先解释一下广度优先遍历在做什么。对于二叉树而言，广度优先搜索(Breadth-First Search, BFS)其实就是二叉树的层序遍历(Level Order Traversal)。层序遍历的过程简单地说就是我们先取出二叉树的第一层全部节点(3)，然后再取出第二层全部节点(9，20)，然后是第三层(15，7)，这样不断地做下去实现对整个二叉树的遍历。
对于这道题而言，我们使用广度优先搜索对二叉树进行遍历，在遍历过程中记录路径最大长度即可。

代码需要的基础知识罗列

题目给出的数据结构，树的定义

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
    }
}

解题用到的代码知识

队列(queue)：一种先进先出(FIFO, First-In-First-Out)的数据结构，可以看成一个排队模型，
排队时排在最后面，出队时最前面的人先离开，因此有先进先出，后进后出
**Java中的队列**
Java集合框架中提供了Queue接口，用于实现队列，Java中队列的主要实现类有ArrayDeque, LinkedList, PriorityQueue
在这里使用LinkedList实现，LinkedList 类实现了 List 和 Deque 接口
它可以作为双向链表使用，也可以作为队列使用。LinkedList 提供了对列表两端的操作支持，这意味着可以在列表的头部或尾部高效地插入和删除元素。
**代码中要使用的方法**:
向队列增加元素的方法：offer()
移除队列元素的方法poll()

算法解析

直接上代码再解释

public int maxDepth(TreeNode root){
    if(root == null){
        return 0;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int ans = 0;
    while(!queue.isEmpty()){
        int size = queue.size();
        while(size > 0){
            TreeNode node = queue.poll();
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
            size --;
        }
        ans++;
    }
    return ans;
}

总体思路

算法入参是根节点root，要求返回结果即最大深度。

先分析这段代码，这里第一个while(大循环)的每一次进行实际上就是对每一层进行遍历并且记录路径长度(ans)（先假设这是对的，后面再细致地考察），也就是如果循环成功进行了一次，就代表二叉树的最大层数最少还能多一层。因此每次循环中都有代码ans++，这表示确实还有更多的层，ans要增加一。最后循环结束以后就得到ans是最终的结果，return返回

代码分解

代码的第一段是判定root是否为空，很明显如果为空的路径长度是0，因此直接return 0即可。
第二段代码主要是两层循环，在循环前先定义了一个队列并将根节点压入队列然后初始化ans为0。我们主要考察代码的每个部分在做什么以及正确性的分析。

这里的循环一共有两层，外层大循环和内存小循环，这里定义了queue存储层的节点。

大循环的第一行代码，这里先假定这行代码获取的是当前处理的层的节点数量（我们还没有对queue究竟保存的是什么进行分析），譬如是第三次进入循环，这里获取的就是第三层的节点数（假定层数从1开始计）。

下面先重点考察内层循环while(size>0)。

 while(size > 0){
     TreeNode node = queue.poll();
     if(node.left != null){
         queue.offer(node.left);
     }
     if(node.right != null){
         queue.offer(node.right);
     }
     size --;
 }

不难发现，每次循环都将取出队列中的节点进行考察，然后将size–，size就是队列中的“当前层”的节点总数（先假定是这样）(注意不是任意时刻队列中全部节点的总数！)。考察时，判定当前层的节点A是否具有左右节点，如果有，将其入队。并且将A出队，所以while(size>0)这个循环结束以后队列中将不存在“当前层”的节点（因为如果存在一定在队列最前端）（size记录的是当前层在队列中的全部节点数，每取出一个节点后都将size–，当size减为0时正好当前层的全部节点全部取完）且此时已完成当前层全部节点的遍历，有因为每次取出一个当前层的节点时都将当前层每个节点的左右子节点入队，所以循环结束时下一层的全部节点都已经入队，队列中全部的节点都是下一层的全部节点。

因此我们总结：内部循环每一次都完成这样一件事：出队全部当前层节点，入队下一层全部节点。为了说明正确性，我们还需要考察第一次进入循环时的性质是否成立，第一次进入循环时（外部大循环），只要树不空（如果是空在代码开头就直接返回，结束），size就是1（队列中只有一个根节点），因此进入循环，判定其左右节点是否存在，如果存在全部入队，并且出队节点自身，所以循环结束以后第二层将进入队列，第一层的节点出队，size–。此时size等于0，符合要求（因为size存储的始终是当前处理的层的节点数，而非队列中的全部节点数！）。而下一次进入循环时将重新获取size，将是第二次的全部节点数。内循环分析结束。

分析完了内部循环，我们就能更清楚地看到外部循环的工作，外部循环每次都获取了队列中的全部节点数量（将要处理的层的全部节点），然后(内部循环)清理当前层的全部节点，并在清理时将其左右子节点（如果存在的话）加入队列，结束后将ans+1。

总结大循环：每次进入是处理一个层的节点，处理结束后清楚当前层的节点并且加入下一层的节点，最后将ans++。这样每处理一层ans都加一，结合ans的初始值0，ans最终将得到路径长度。

分析完了两个循环的作用，我们现在可以考察整体算法的正确性了，算法开头如果root是空，返回0，很明显这是正确的。对于root非空的情况，这里使用循环不变式辅助论证。

循环不变式论证

这部分内容参考了算法导论后进行撰写，有错误之处欢迎指出

我们定义循环不变式:在每次循环结束后，变量ans都始终表示从根节点到当前处理层的路径长度。

初始情况：在循环开始前，队列中仅有root，此时ans为0，ans 的值表示从根节点到当前层（此时还没有开始处理任何节点，因此当前层是根节点）的路径长度为 0，满足循环不变式的定义。
保持：根据前面的分析，每次循环我们都处理当前层的节点，同时出队当前层全部节点，并将下一层全部节点加入队列，增加ans的值1。因此当每次循环都将处理的层数+1，ans也+1，循环不变式成立。
终止：很明显循环的终止条件是队列为空，根据前面的分析只有当前层的全部节点都没有子节点时队列才会空（因为循环后队列中存储的是下一层的全部节点，既然队列为空，表面下一层没有节点）。这就是说此时所有层的节点都已经被处理完毕了，且每处理一层ans就将加1，所以此时ans就是根节点到最后一层节点的路径长度。并且在队列为空后ans就停止增加，因此ans将保持为路径长度。很明显ans保持循环不变式定义。

因此算法结束以后ans确实代表了从根节点到最远路径。至此算法正确性得以说明。

算法再解释

以上从代码分析的角度分析考察了广度优先搜索的工作流程，这里再从算法本身的角度说明如何撰写代码。
第一步判定根节点是否为空。
然后，首先我们需要定义队列保存每次需要处理的层的节点（第一层即直接将根节点入队），并且定义ans记录。然后进行循环，每次循环时处理当前层的全部节点（大循环），逐个取出当前层的节点并且将下一层节点全部加入队列（小循环），由于我们无法从队列本身判断出队是否应该结束，因此引入变量size在小循环开始前记录队列中的当前层节点总数，每取出一个都将size–，这样当size为0时表明已经全部取出。同时用变量记录已经经过的路径长度，这样当大循环结束时ans就表示走过的路径长度。

全文完

引用内容
[1]https://leetcode.cn/problems/maximum-depth-of-binary-tree/solutions/349250/er-cha-shu-de-zui-da-shen-du-by-leetcode-solution/
[2][1]Thomas,H.Cormen,Charles,E.Leiserson,Ronald,L.Rivest,Clifford,Stein,殷建平,徐云,王刚,刘晓光,苏明,邹恒明,王宏志.算法导论(原书第3版)[J].计算机教育, 2013(10):1.DOI:CNKI:SUN:JYJS.0.2013-10-014.