Leetcode - 1161. Maximum Level Sum of a Binary Tree

문제

바이너리 트리에서 각 level의 합을 구했을때, 가장 큰 값을 갖는 level을 리턴하라. (level은 1부터 시작)

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

아이디어

• DFS: O(n)
  각 level의 합을 저장하는 배열을 만들고 DFS순회 하면서 더하기.

풀이

class Solution {
public:
    int freq[1001] = {0};
    int maxval = INT_MIN;
    int maxhgt = 0;
    
    void traval(TreeNode *root, int lv) {
        if (!root)
            return;
        freq[lv] += root->val;
        if (lv > maxhgt)
            maxhgt = lv;
        traval(root->left, lv + 1);
        traval(root->right, lv + 1);
    }
    int maxLevelSum(TreeNode* root) {
        int maxlv = 0;
        traval(root, 1);
        for (int i = 1; i <= maxhgt; i++) {
           if (freq[i] > maxval) {
               maxval = freq[i];
               maxlv = i; 
           }
        }
        return maxlv;
    }
};