題目
You need to find the largest value in each row of a binary tree.
Example:
1 2 3 4 5 6 7 8 9 |
<b>Input:</b> 1 / \ 3 2 / \ \ 5 3 9 <b>Output:</b> [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); } } |