[LeetCode] 515. Find Largest Value in Each Tree Row

 

https://leetcode.com/problems/find-largest-value-in-each-tree-row/description/

Find Largest Value in Each Tree Row - LeetCode

leetcode - Find Largest Value in Each Tree Row

문제 유형 : 트리 / BFS / DFS

문제 난이도 : Medium

 

문제

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

 

이진 트리의 루트가 주어진다. 트리의 각 레벨별로 최대값을 담은 배열을 반환하시오. 0-indexed의 형태로.

 

풀이

BFS를 통해서 풀어줄 수 있다.

핵심은 BFS를 끊어서 한다는건데, 탐색 전에 큐의 크기를 재놓고, 딱 그 정도만 하면, 레벨별로 분류를 할 수 있다.

 

코드

C++

 

/**
 * 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:
    vector<int> largestValues(TreeNode* root) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        vector<int> largestVals;
        queue<TreeNode*> q;
        if(root == nullptr) return {};

        q.push(root);

        while(!q.empty()) {
            int repeat = q.size();
            int maxVal = INT_MIN;
            for(int i = 0; i < repeat; i++) {
                auto curr = q.front();
                q.pop();
                maxVal = max(maxVal, curr -> val);
                if(curr -> left != nullptr) {
                    q.push(curr -> left);
                }

                if(curr -> right != nullptr) {
                    q.push(curr -> right);
                }
            }

            largestVals.push_back(maxVal);
            
        }
        
        return largestVals;
    }
};