6.层序遍历

• 2.11

  • 秒了

• 1.26

  • 秒了

• 1.16

  • 依旧两点忘了，第一：需要每层 for 循环取出，第二：先记录长度，再进入 for 循环，不然 for 的边界会自动 变化
  • 有进步，会用 api 了

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null) return res;
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int size = q.size();
            for(int i=0;i<size;i++){
                TreeNode temp = q.poll();
                list.add(temp.val);
                if(temp.left!=null){
                    q.offer(temp.left);
                }
                if(temp.right!=null){
                    q.offer(temp.right);
                }
            }
            res.add(list);
        }
        return res;
        
    }
}

• 11.11
  • 需要在一个for循环中弹出队列,并且提前记录size值!,因为for中会添加节点,不能是之一直变

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

• 不能用遍历了,改用队列
• 队列使用LinkedList实现,返回值为Queue
• 记住Queue的offer和poll方法
• 需要在while循环中取出node,判断node的子节点