广度优先遍历

遍历二叉树的另一个方式，广度优先遍历；实际上这个遍历方式还有一个名字叫做 层序优先遍历
如果说深度优先遍历是一条路走到黑的话…广度优先遍历则是一层一层的遍历，除非遍历完成当前的层，是不会向下在进行遍历的；

题目

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

分析

在深度优先遍历中，通过一个节点，寻找其子节点，这就造成了除非某个节点没有子节点，那么就会一直向下进行遍历，广度优先就不能这样了….需要先遍历完成一层；广度优先遍历有两种解决方案

1. 最直观的方法….迭代器遍历，使用一个二元组表示一个节点元素，这个二元组将包含两种信息：节点的深度和节点的内容，将这个二元组依次存放在queue中，然后一层一层取出

2. 使用递归方式进行

   例子

   2
   1 3
   4

   方式一：iterator

   分析：

3. 创建两个buffer：queue，以及一个结果buffer；

4. 将根节点二元组存放在队列中
5. 进入第一轮循环
6. 判断当前queue中是null，如果是null，break；
7. 判断当前队列中的节点是否存在子节点？ 只要队列中存在一个有子节点的节点就算存在子节点
8. 当前队列中仅有一个root，根节点确实存在子节点，将根节点移出queue放入结果buffer中，然后把它的子节点存入queue；
9. 进入第二轮循环
10. 判断当前queue中是null？不是，继续向下执行
11. 判断当前queue中的节点是否存在子节点？是，节点3拥有一个子节点4
12. 将当前queue中的内容移入buffer；然后将子节点放入queue中；
13. 进入第三轮循环
14. 当前queue中是null？不是，继续向下执行
15. 判断当前queue中的节点是否存在子节点？否
16. 将queue中的内容移入buffer；break；
17. 结束

时间复杂度位O(n)，空间复杂度位O(n)

方式二：递归

递归的思路就类似于深度优先算法了…

1. 创建一个list，先向其中添加一个list对象；
2. 第一次方法调用
3. 将 根节点 & 当前深度 （1）传入方法中；
4. 判断list的sie<=当前深度？如果小于就什么也不干：如果大于就要往list中add一个新的list对象；
5. 把该节点放在list中的index==0的的list中；
6. 判断根节点是否拥有左子节点？
7. 拥有左子节点，将 左子节点 & 当前深度+1 （2），作为参数，传入方法中；
8. 第二次方法调用
9. 判断list的sie<=当前深度？如果小于就什么也不干：如果大于就要往list中add一个新的list对象；这里深度==2；但是list的size仅仅有1；因此要插入一个新的list对象了；
10. 将这个节点放入index==1的list中；
11. 判断该节点是否拥有左子节点？没有
12. 判断该节点是否拥有右子节点？没有
13. 结束第二次调用；
14. 回到第一次调用中
15. 判断节点是否存在右子节点？
16. 拥有右侧子节点，将 右子节点 & 当前深度+1 （2），作为参数，传入方法中；
17. 第三次方法调用
18. 判断list的sie<=当前深度？如果小于就什么也不干：如果大于就要往list中add一个新的list对象；这里深度==2；由于在第二次方法调用中我们已经完成了对list扩充的任务，因此到这里就可以了；
19. 将这个节点插入到index==1的list中；
20. 判断该节点是否拥有左子节点？没有
21. 判断该节点是否拥有右子节点？拥有；因此还要继续向下进行；将 右子节点 & 当前深度+1 （3），作为参数，传入方法中；
22. 第四次方法调用
23. 判断list的sie<=当前深度？如果小于就什么也不干：如果大于就要往list中add一个新的list对象；这里深度==3；明显list又不够用了…继续向其中添加一个list对象
24. 将当前这个list存放到index==2的list中；
25. 判断是否存在左子节点？没有
26. 判断是否存在右子节点？没有
27. 结束运行；
28. 回到第三次调用中
29. 结束运行
30. 回到第一次调用中
31. 结束运行；

方法结束， 时间复杂度为O(n)空间复杂度为O(树的高度)

对比

从复杂度来考虑的话…好像是使用遍历会更优，但是考虑到list自动扩容的问题….也不一定就是优势了….
而且，实际上使用递归进行的广度优先遍历…仅仅是再结果上完成了任务 看起来好像是广度优先的遍历，但是实际上，使用递归这种方式，本质上还是一个深度优先的应用，如果真的是广度优先遍历，要用来查询某个位于树中层的数据，递归的用法还是不如迭代实现的真正的广度优先算法

代码

这里就实现一下使用递归的方法吧…

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        return ret;
    }
}