102. 二叉树的层序遍历：树的BFS（队列迭代）、代码优化思路以及教训.md

题目简述：

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

题目链接：102. 二叉树的层序遍历

BFS

BFS的关键是使用队列数据结构！！！

根据BFS的直接定义，不难写出以下代码：

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */


class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> oldQueue = new LinkedList<>();
        Queue<TreeNode> newQueue = new LinkedList<>();
        oldQueue.offer(root);
        List<Integer> valList = new ArrayList<>();

        while (true) {
            try {
                TreeNode node = oldQueue.remove();
                valList.add(node.val);
                if (node.left != null) newQueue.offer(node.left);
                if (node.right != null) newQueue.offer(node.right);
            } catch (Exception e) {
                res.add(valList);
                valList = new ArrayList<>();
                oldQueue = newQueue;
                newQueue = new LinkedList<>();
                if (oldQueue.isEmpty()) break;
            }
        }

        return res;
    }
}

但这份代码性能很差。大部分在平台上提交的代码都只需要1ms即可通过测试，而这份代码却需要11ms才能执行完毕。是什么导致的呢？

优化思路和教训

其实，最主要的问题是在循环代码里使用了异常处理控制流程，这造成了十分严重的性能瓶颈。Java中异常捕获是非常重量级的操作，每次触发异常都会生成堆栈轨迹，严重影响性能。一般来说，1次异常捕获需要约1-5微秒，而1次条件判断则仅需几纳秒。当树有N层时，刚才的代码会触发N次异常，造成极大的性能开销。

将 remove() 替换为不会抛出异常而是在队列空时返回null的 poll 并修改异常捕获的逻辑即可解决问题，以下代码仅用时1ms：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> oldQueue = new LinkedList<>();
        Queue<TreeNode> newQueue = new LinkedList<>();
        oldQueue.offer(root);
        List<Integer> valList = new ArrayList<>();

        while (true) {
            TreeNode node = oldQueue.poll();
            if (node != null) {
                valList.add(node.val);
                if (node.left != null) newQueue.offer(node.left);
                if (node.right != null) newQueue.offer(node.right);
            } else {
                res.add(valList);
                valList = new ArrayList<>();
                oldQueue = newQueue;
                newQueue = new LinkedList<>();
                if (oldQueue.isEmpty()) break;
            }
        }

        return res;
    }
}

使用信号量的更好实现

现在我们的代码时间开销已经很小了，但内存还可以再优化——虽然无伤大雅，区别很小，但原来的写法不够优雅。这个原因主要是我们使用了两个队列切换以在遍历时并行地让当前层节点出队、当前子节点的子节点入队。但实际上我们只需要一个队列就够了，并不需要频繁地 new 新的队列对象。我们只需要维护一个变量，使该变量记录下一层节点的数量，当下一层出队的节点数达到该值，我们就知道接下来出队的节点是属于下下一层的了。

如下代码所示：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int len = 1;
        int index = 0;
        int nextLen = 0;
        List<Integer> valList = new ArrayList<>();

        while (true) {
            if (index < len) {
                TreeNode node = queue.poll();
                valList.add(node.val);
                if (node.left != null) {queue.offer(node.left); nextLen++;}
                if (node.right != null) {queue.offer(node.right); nextLen++;}
                index++;
            } else {
                res.add(valList);
                if (queue.isEmpty()) break;
                valList = new ArrayList<>();
                len = nextLen;
                index = 0;
                nextLen = 0;
            }
        }

        return res;
    }
}

这份代码对内存的利用就比较高效了。这也是最推荐的写法。