二叉树层序遍历

102. 二叉树的层序遍历

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

107. 二叉树的层序遍历 II

• 使用 LinkedList> res = new LinkedList<>();

• res.addFirst(path);

  class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> res = new LinkedList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            List<Integer> path = new ArrayList<>();
            int qsize = q.size();
            while(qsize != 0){
                TreeNode node = q.poll();
                path.add(node.val);
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
                qsize--;
            }
            res.addFirst(path);
        }
        return res;
    }
  }

  103. 二叉树的锯齿形层序遍历

  在层序遍历的基础上，偶数层Collections.reverse(path)即可

  class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        int level = 1;
        while(!q.isEmpty()){
            List<Integer> path = new ArrayList<>();
            int qsize = q.size();
            while(qsize != 0){
                TreeNode node = q.poll();
                path.add(node.val);
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
                qsize--;
            }
           if(level % 2 == 0) Collections.reverse(path);  
            res.add(path);
            level++;
        }
        return res;
    }
  }
  

  199. 二叉树的右视图

  class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            int qsize = q.size();
            while(qsize != 0){
                TreeNode node = q.poll();
                if(qsize == 1) res.add(node.val);
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
                qsize--;
            }
        }
        return res;
    }
  }
  

  637. 二叉树的层平均值

  class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            double sum = 0;
            int qsize = q.size(), num = qsize;
            while(qsize > 0){
                TreeNode node = q.poll();
                sum += node.val;
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
                qsize--;
            }
            res.add(sum / num);
        }
        return res;
    }
  }
  

  515. 在每个树行中找最大值

  class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            int max = Integer.MIN_VALUE;
            int qsize = q.size(), num = qsize;
            while(qsize > 0){
                TreeNode node = q.poll();
                max = Math.max(max, node.val);
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
                qsize--;
            }
            res.add(max);
        }
        return res;
    }
  }
  

  116. 填充每个节点的下一个右侧节点指针

  这题可以用BFS来做，和上面的题目，一个做法，空间O(n)，题目要求O1空间
  BFS

  class Solution {
    public Node connect(Node root) {
        Queue<Node> q = new LinkedList<>();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            int qsize = q.size();
            while(qsize > 0){
                Node node = q.poll();
                if(qsize == 1) node.next = null;
                else node.next = q.peek();
  
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
                qsize--;
            }
        }
        return root;
    }
  }
  

  

  class Solution {
    public Node connect(Node root) {
        if(root == null) return root;
        Node leftroot = root;
        //完美二叉树，有left证明就有下一层，要把下一层的指针的next都更新一下
        //1的left为2，证明有下一层，把下一层的next都更新
        while(leftroot.left != null){
            //p为每层最左侧的点【1，2，4.。。。
            for(Node p = leftroot; p != null; p = p.next){
                //p为2，将4的next指向5
                p.left.next = p.right;
                if(p.next != null){
                    //p为2，将5的next指向3的left就是6，首先判断3在不在
                    p.right.next = p.next.left;
                }
            }
            //更新到下一层,1结束到2，2结束到4
            leftroot = leftroot.left;
        }
        return root;
    }
  }
  

  117. 填充每个节点的下一个右侧节点指针 II

• 这题就不是完美二叉树了

• 上一题用队列BFS也可以通过这一题