1.连续遍历

1.1题目描述

参考答案

1.2解题思路

• 层序遍历BFS一般都是需要用队列来辅助实现，不同于深度优先DFS，BFS一般是不用递归的。递归会导致越来越深入，不符合广度优先

• 第一行入队————》pop取queue中的node——》取值——》node的left right 入队

• 此时队列中的顺序符合BFS

• 循环，queue继续pop取node——》取值——》该node的left right继续入队

• 如此循环pop并入队，队列中的顺序一直符合BFS

1.2.1创建Queue的技巧

• Queue是一个接口，不能直接实例化

• 因为LinkedList实现了Queue接口，可以用其实例化

• {外部这个大括号表示匿名对象,可以在这一层进行@Overide {内部这个大括号相当于在外面调用this.add()} }

    LinkedList integers = new LinkedList() {//匿名对象
  
        @Override public boolean add(Integer integer) {
            return super.add(66666);//这会导致所有的add都是添加66666
        }
  
        {//这一层的{}相当于在外层写add
            add(1);
            add(2);
            add(3);
        }
    };
    integers.add(4);
    integers.add(5);
    integers.add(6);
    integers.add(7);
    System.out.println(integers);//一共有3+4=7条
    //[66666, 66666, 66666, 66666, 66666, 66666, 66666]
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

因此我们可以直接

    Queue queue = new LinkedList<>(){
        {
            add(root);
        }
    };
1
2
3
4
5

1.2.2需要注意的点

• 返回一个空int[ ] 是直接return new int[]{}；
• 队列的弹出API是 queue.poll()

最终代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        //第一步永远是判断是否空
        if(root == null) return new int[]{};
        //ArrayList方便添加元素，最后转int[]即可
        ArrayList list = new ArrayList();
        //用Queue来存储BFS的节点,利用匿名对象内部{}初始化
        Queue queue = new LinkedList(){
            {
                add(root);
            }
        };
        //因为最开始 每次循环只pop一次，但是可能会添加多次
        //最后一次pop时早已没有添加的
        //所以可以用!queue.isEmpty()作为判断条件
        while(!queue.isEmpty()){
            TreeNode now = queue.poll();//当前节点
            list.add(now.val);
            //添加完成当前节点值后，往queue增加节点
            if(now.left != null) queue.add(now.left);
            if(now.right != null) queue.add(now.right);
        }
        int[] dest = new int[list.size()];
        for(int i = 0 ; i < list.size() ; i++){
            dest[i] = list.get(i);
        }
        return dest;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

2.分层遍历

2.1题目描述

与上一题不同，这一题需要一层一行，最终返回一个二维list

其内层的每个List，都是二叉树的一整层

参考答案

2.2解题思路

• while每次循环都必须要new一个内层List
• while每次循环都要把这个new出来的内层List填满

2.2.1分析和第一题的差异

• 第一题中，while中没有new 一个List

        while(!queue.isEmpty()){
            TreeNode now = queue.poll();//当前节点
            list.add(now.val);
            //添加完成当前节点值后，往queue增加节点
            if(now.left != null) queue.add(now.left);
            if(now.right != null) queue.add(now.right);
        }
  1
  2
  3
  4
  5
  6
  7

• 第一次改造，发现每次while循环只往temp中添加了一个元素

        while(!queue.isEmpty()){
    ——————————》    ArrayList temp = new ArrayList();
            TreeNode now = queue.poll();//当前节点
     ——————————》       temp.add(now.val);
            if(now.left != null) queue.add(now.left);
            if(now.right != null) queue.add(now.right);
        }
  1
  2
  3
  4
  5
  6
  7

• 第二次改造，每次把当前queue中的元素全部poll到temp中要先固定for循环的次数

        while(!queue.isEmpty()){
   		 ArrayList temp = new ArrayList();
   	————》 for(int i = 0 ; i < queue.size() ; i++){//因为for循环的内部会往queue添加元素，所以要先固定for循环的次数
            TreeNode now = queue.poll();//当前节点
    		  temp.add(now.val);
            if(now.left != null) queue.add(now.left);
            if(now.right != null) queue.add(now.right);
       ————》     }
        }
  1
  2
  3
  4
  5
  6
  7
  8
  9

2.2.2需要注意的点（集合for循环的开始条件）

所有跟集合相关的for循环开始条件，都必须先int i = size()，因为size可能会在for循环的过程中变动

2.2.3最终结果

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List> levelOrder(TreeNode root) {

        List> destList =  new ArrayList>();
        //先判断root==null的情况
        if(root == null) return destList;

        //创建TreeNode的队列
        Queue queue = new LinkedList(){
            {
                add(root);//初始化
            }
        };

        //while循环 内层for循环填满每个temp
        while(!queue.isEmpty()){
            ArrayList temp = new ArrayList();

          //  for(int i = 0 ; i < queue.size() ; i++){queue.size()在随元素弹出的过程中动态变化
            for(int i = queue.size() ; i > 0 ; i--){//固定for循环的次数,保证循环的是本层
            TreeNode now = queue.poll();
            temp.add(now.val);

            //往queue中添加下一层的元素（完整的for循环之后，queue中刚好只有下一层的所有元素）
            if(now.left != null) queue.add(now.left);//防止被这两条影响temp长度
            if(now.right != null) queue.add(now.right);//防止被这两条影响temp长度
            }

            destList.add(temp);
        }
        return destList;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

3.分层交叉遍历

3.1简单粗暴直接reverse()

3.1.1取余位运算

当x=2^n(n为自然数)时，

a % x = a & (x - 1 )

3.1.2Collections.reverse()

但是leetcode中用不了Collections工具包

3.2最终写法:链表（双端队列）