当前位置：网站首页>二叉树的三种层序遍历BFS

二叉树的三种层序遍历BFS

2022-07-20 22:54:00 【ZJH'blog】

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<Integer> integers = new LinkedList<Integer>() {//匿名对象

      @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]

因此我们可以直接

    Queue<TreeNode> queue = new LinkedList<>(){
        {
            add(root);
        }
    };

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<Integer> list = new ArrayList<Integer>();
        //用Queue来存储BFS的节点,利用匿名对象内部{}初始化
        Queue<TreeNode> queue = new LinkedList<TreeNode>(){
            {
                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;

    }
}

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);
      }

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

      while(!queue.isEmpty()){
  ——————————》    ArrayList<Integer> temp = new ArrayList<Integer>();
          TreeNode now = queue.poll();//当前节点
   ——————————》       temp.add(now.val);
          if(now.left != null) queue.add(now.left);
          if(now.right != null) queue.add(now.right);
      }

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

      while(!queue.isEmpty()){
 		 ArrayList<Integer> temp = new ArrayList<Integer>();
 	————》 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);
     ————》     }
      }

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<List<Integer>> levelOrder(TreeNode root) {

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

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

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

          //  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;

    }
}