二叉树专题刷题

二叉树的层平均值

题目

637. 二叉树的层平均值 - 力扣（LeetCode）

解题思路

使用三个集合，sums集合存储每层的总和，count集合存储每层的节点数，averages存储每层的平均值。

这里要讲一下add方法和set方法的区别

add方法：用于向集合的末尾插入新的元素，是List接口中最常用的插入方法

set方法：本质上是一种替换操作， 要设置某个位置上的元素，这个位置必须已存在，否则会抛出异常

代码

 public List<Double> averageOfLevels(TreeNode root) {
        List<Integer> count = new ArrayList<>();
        List<Double> sums = new ArrayList<>();
        List<Double> averages = new ArrayList<>();
        dfs(root,0,sums,count);
        for(int i=0;i<sums.size();i++){
            averages.add(sums.get(i)/count.get(i));
        }
        return averages;
    }

    private void dfs(TreeNode root, int i, List<Double> sums, List<Integer> count) {
        if(root == null){
            return;
        }
        if(i>=sums.size()){
            sums.add(1.0*root.val);
            count.add(1);
        }else{
            sums.set(i,sums.get(i)+root.val);
            count.set(i,count.get(i)+1);
        }
        dfs(root.left,i+1,sums,count);
         dfs(root.right,i+1,sums,count);
    }

二叉树的层序遍历

题目

102. 二叉树的层序遍历 - 力扣（LeetCode）

解题思路

使用先进先出队列，每次都重置队列长度，使每次队列里都是每层的节点

代码

  public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> sum = new ArrayList<>();
        if(root==null)
            return sum;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; 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);
                }
            }
            sum.add(level);
        }

        return sum;
    }

二叉树的锯齿型层序遍历

题目

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

解题思路

使用depue双端队列，两端都可进。只需按照奇偶性，从不同端入队即可。

代码

 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> sum = new ArrayList<>();
        if(root==null)
            return sum;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean flag = false;
        while (!queue.isEmpty()) {
            Deque<Integer> level = new LinkedList<Integer>();
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                TreeNode node = queue.poll();
                if(!flag){
                    level.offerLast(node.val);
                }else{
                    level.offerFirst(node.val);
                }
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            sum.add((List<Integer>) level);
            flag=!flag;
        }

        return sum;
    }

二叉树的右视图

题目

199. 二叉树的右视图 - 力扣（LeetCode）

解题思路

我的思路相当暴力，只需要进行层序遍历，然后获取每层最右边的节点

代码

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null)
            return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; 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);
                }
            }
            list.add(level.get(level.size()-1));
        }
        return list;
    }