Maximum Level Sum of a Binary Tree[M,Tree,Depth-First Search,Breadth-First Search,Binary Tree]

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

 

Example 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.

Example 2:

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105

1. Python

 

Deepest leave sum 문제랑 비슷해서 풀었다.

문제도 계속 머리박고 풀다보니까 돌고 도는듯 하다;;ㅎㅎ

근데 파이썬으로도 이 정도면 C/C++로는 얼마나 복잡할꼬 ㅠㅠㅠ

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        dic = {}
        lv = 1
        while q:
            size = len(q)
            dic[lv] = 0
            for _ in range(size):
                curr = q.popleft()
                if curr.left:
                    q.append(curr.left)
                if curr.right:
                    q.append(curr.right)
                dic[lv] += curr.val
            lv += 1
        val=-(10**5-1)
        ans=0
        for k,v in dic.items():
            if v > val :
                val = v
                ans = k
        return ans

 

 

대세에 지장은 없지만,

굳이 dic을 안 쓰고도 문제를 풀 수는 있다.

Runtime이 좀 더 빠름

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        # dic = {}
        minsum = -(10**5-1)
        lv = 1
        while q:
            size = len(q)
            currsum = 0
            for _ in range(size):
                curr = q.popleft()
                if curr.left:
                    q.append(curr.left)
                if curr.right:
                    q.append(curr.right)
                currsum += curr.val
            if currsum > minsum:
                minsum = currsum
                maxlv = lv
            lv += 1
        return maxlv

 

2. C

 

C로는 queue를 쓰지 못하니까 코드가 개판이다. Recursive를 사용하였다.

 

void dfs(struct TreeNode* root, int level, int* levelSums, int* maxLevel) {
    if (root == NULL) {
        return;
    }

    // 현재 레벨의 합 계산
    levelSums[level] += root->val;

    // 최대 레벨 갱신
    if (level > *maxLevel) {
        *maxLevel = level;
    }

    // 왼쪽과 오른쪽 자식 노드로 재귀 호출
    dfs(root->left, level + 1, levelSums, maxLevel);
    dfs(root->right, level + 1, levelSums, maxLevel);
}

// 최대 레벨 합을 찾는 함수 정의
int maxLevelSum(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    // 레벨 합을 저장할 배열 크기 지정 (가정: 트리의 최대 높이는 10000 이하)
    int levelSums[10000] = {0};
    int maxLevel = 0;

    // DFS 호출하여 각 레벨의 합 계산
    dfs(root, 1, levelSums, &maxLevel);

    // 최대 합을 갖는 레벨 찾기
    int maxSum = INT_MIN;
    int maxSumLevel = 1;
    for (int i = 1; i <= maxLevel; i++) {
        if (levelSums[i] > maxSum) {
            maxSum = levelSums[i];
            maxSumLevel = i;
        }
    }

    return maxSumLevel;
}

 

 

3. C++ 

 

C++은 queue,stack을 지원하니까 좀 편하다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        if(!root) return 0;

        queue<TreeNode*> q;
        q.push(root);
        int val = INT_MIN;
        int lv=1;
        int ans;
        while(!q.empty()){
            int size = q.size();
            int currsum = 0;
            for(int i=0;i<size;i++){
                TreeNode* curr = q.front();
                q.pop();
                currsum = currsum + curr->val;
                if(curr->left) q.push(curr->left);
                if(curr->right) q.push(curr->right);
            }
            if(currsum > val){
                val = currsum;
                ans = lv;
            }
            lv++;
        }
        return ans;
    }
};