[Binary Tree-BFS][Medium] 1161. Maximum Level Sum of a Binary Tree

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

Maximum Level Sum of a Binary Tree - LeetCode

 

Q. 주어진 트리에서 root 노드의 레벨을 1, 이하로 2, 3 같이 1씩 증가 한다고 할때, 

 각 레벨의 노드합이 최대인 레벨의 최소 레벨을 구하라.(루트에서 가장 가까운 레벨을 찾아라.)

 

Solution. 

 queue를 이용한 트리의 레벨 서치 방법을 안다면, 쉽게 풀 수 있는 문제. 

다만 수의 범위 등, 특정 조건에 유의하자.

 

int maxLevelSum(TreeNode* root)
{
    if (root == NULL)	return 0;

    queue<TreeNode*> qBuff;
    qBuff.push(root);
    int level = 0;
    long maxSum = LONG_MIN;
    int ret = 0;
    while (!qBuff.empty())
    {
        ++level;
        int count = qBuff.size();
        long sum = 0;
        for (int q = 0; q < count; ++q)
        {
            TreeNode* cur = qBuff.front();
            qBuff.pop();

            sum += cur->val;
            if (cur->left != NULL)	qBuff.push(cur->left);
            if (cur->right != NULL)	qBuff.push(cur->right);
        }

        if (maxSum < sum)
        {
            maxSum = sum;
            ret = level;
        }
    }
    return ret;
}

 

 

Result.