637 Average of Levels in Binary Tree

637. Average of Levels in Binary Tree

1. Question

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

Input:

    3
   / \
  9  20
    /  \
   15   7

Output:
 [3, 14.5, 11]

Explanation:

The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Note:

1. The range of node's value is in the range of 32-bit signed integer.

2. Implementation

(1) BFS

public class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            double sum = 0;
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.remove();
                sum += curNode.val;

                if (curNode.left != null) {
                    queue.add(curNode.left);
                }

                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            res.add(sum / size);
        }
        return res;
    }
}

(2) DFS

思路：主要是维护两个数组，分别记录每一层的levelSum， 和对应的size

public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        int height = getHeight(root);
        long[] levelSum = new long[height];
        int[] size = new int[height];

        getLevelAverage(root, 0, levelSum, size);

        for (int i = 0; i < height; i++) {
            res.add(levelSum[i] * 1.0 / size[i]);
        }
        return res;
    }

    public void getLevelAverage(TreeNode node, int depth, long[] levelSum, int[] size) {
        if (node == null) {
            return;
        }

        levelSum[depth] += node.val;
        size[depth] += 1;

        getLevelAverage(node.left, depth + 1, levelSum, size);
        getLevelAverage(node.right, depth + 1, levelSum, size);
    }

    public int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }

3. Time & Space Complexity

BFS: 时间复杂度: O(n), 空间复杂度：O(w)，w是一行里有最多的node的个数

DFS: 时间复杂度: O(n), 空间复杂度：O(h), h是树的高度