标签搜索

目 录CONTENT

文章目录

【算法模板】 树的广搜

陈铭
2022-02-04 / 0 评论 / 0 点赞 / 109 阅读 / 267 字 / 正在检测是否收录...

例题: 二叉树的层平均值

力扣673题为例:
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
##示例:
image

输出:[3.00000,14.50000,11.00000]
**解释:**第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> averages = new ArrayList<Double>();
		// 染色法记录染色边界的队列
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
		// 套路:while (!queue.isEmpty())
        while (!queue.isEmpty()) {
            double sum = 0;
            int size = queue.size();
			// 遍历队列
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            averages.add(sum / size);
        }
        return averages;
    }
}
0

评论区