愛比的新手筆記

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

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.

和 [LeetCode] 107. Binary Tree Level Order Traversal II 這題很像,

那題是列出每層的數字, 那延伸出來就是將每層數字平均, 所以直接拿那題的code來就可以用了

public List<double> AverageOfLevels(TreeNode root)
{
    List<double> rst = new List<double>();
    List<List<int>> lst = LevelOrder(root);
    foreach (List<int> vals in lst)
    {
        int i = 0;
        double x = 0;
        for (; i < vals.Count; i++)
        {
            x += vals[i];
        }
        rst.Add(x / i);
    }
    return rst;
}

private List<List<int>> LevelOrder(TreeNode root)
{
    List<List<int>> rst = new List<List<int>>();
    if (root == null) return rst;
    rst.Add(new List<int>(new[] { root.val }));
    return LevelOrder(root, rst, 1);
}

private List<List<int>> LevelOrder(TreeNode root, List<List<int>> rst, int i)
{
    if (root == null) return rst;
    List<int> lst = null;
    if (rst.Count >= ++i)
        lst = rst[i - 1];
    else
        lst = new List<int>();
    if (root.left != null)
        lst.Add(root.left.val);
    if (root.right != null)
        lst.Add(root.right.val);
    if (lst.Count > 0 && !rst.Contains(lst))
        rst.Add(lst);
    return LevelOrder(root.right, LevelOrder(root.left, rst, i), i);
}

 

Taiwan is a country. 臺灣是我的國家