2022-08-13 【我的刷题日记】LeetCode 199 二叉树的右视图 637 二叉树的层平均值

同样使用层序遍历的思路 在最后添加结果集之前 增加一个判断 当遍历到每层最后一个元素的时候 才添加到结果集

class Solution {
    public List<Integer> result = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        levelOrderOne(root);
        return result;
    }
      public void levelOrderOne(TreeNode root){
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            while(size > 0){
                TreeNode temp  = queue.poll();
                if (temp.left != null) queue.add(temp.left);
                if (temp.right != null) queue.add(temp.right);
                size--;
                // 当遍历到每层的最后一个节点的时候 加入结果集
                if(size == 0) {
                    result.add(temp.val);
                }
            }
        }

    }
}

整体依旧使用层序遍历模板 添加sum记录每层的数值和 和备份的sizenum用于记录每层的节点个数

class Solution {
   public List<Double> res = new ArrayList<>();
    public List<Double> averageOfLevels(TreeNode root) {
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            int sizenum = size;
            Double sum = 0d;
            while (size > 0) {
                TreeNode temp = queue.poll();
                // 平均数等于每层的累加sum除以每层的个数size
                // 每次弹出一个就记录值到sum中
                sum+=temp.val;
                if (temp.left != null)  queue.add(temp.left);

                if (temp.right != null) queue.add(temp.right);
                size--;
            }
            // 一层弹出完成之后 计算平均值 加入res中
            Double avg = sum/sizenum;
            res.add(avg);
        }
        return res;
    }
}