題目

You need to find the largest value in each row of a binary tree.

Example:

Input: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]

解題過程

這題要找出二元樹中同階層最大的數字，我的作法是先將每層的數字收集起來，最後再一起比較。

答案

Dictionary<int, List<int>> dict = new Dictionary<int, List<int>>();

public IList<int> LargestValues(TreeNode root)
{
    List<int> list = new List<int>();

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

    list.Add(root.val);
    FindNum(0, root.left, root.right);
    list.AddRange(dict.Keys.Select(x => dict[x].Max()));

    return list;
}

public void FindNum(int idx, TreeNode left, TreeNode right)
{
    if (left == null && right == null)
    {
        return;
    }

    if (!dict.ContainsKey(idx))
    {
        dict[idx] = new List<int>();
    }

    if (left != null)
    {
        dict[idx].Add(left.val);
        FindNum(idx + 1, left.left, left.right);
    }

    if (right != null)
    {
        dict[idx].Add(right.val);
        FindNum(idx + 1, right.left, right.right);
    }
}