[C#] 1161. Maximum Level Sum of a Binary Tree

 

1. 문제

 

이진 트리인 root가 주어지고, 루트의 레벨은 1, 자식의 레벨은 2가 되는 식이다.

각 레벨 노드들의 합이 가장 큰 레벨 중 가장 작은 레벨인 x를 반환하라.

 

 

---

 

2. 풀이 과정

 

트리를 전위순회 하며 각 노드의 값들을 dictionary에 레벨별로 누적시켜 저장한다.

 

가장 큰 합이면서 가장 작은 레벨을 반환해야 하므로 dictionary의 value를 내림차순으로 정렬한 뒤 key를 오름차순으로 정렬하여 dictionary의 첫 키값을 반환한다.

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MaxLevelSum(TreeNode root) {
        var dict = new Dictionary<int, int>();
        var floor = 0;

        Find(root);

        void Find(TreeNode node)
        {
            if(node == null)
            {
                return;
            }

            floor++;

            if(!dict.TryAdd(floor, node.val))
            {
                dict[floor] += node.val;
            }

            Find(node.left);
            Find(node.right);

            floor--;
        }

        return dict.OrderByDescending(x => x.Value).ThenBy(x => x.Key).First().Key;
    }
}