[C#][LeetCode] 515. Find Largest Value in Each Tree Row

題目

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]

解題過程

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

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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);
}
}