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

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

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

풀이

• rowMax를 -987654321이 아닌, $<$limits$>$의 INT_MIN 상수를 이용해 초기화해야 한다
  (조건: -2^31 <= Node.val <= 2^31 - 1)

• node가 없는 binary tree가 input으로 들어올 수 있다
  (조건: The number of nodes in the tree will be in the range [0, 104])

INPUT: root=[]
OUTPUT: []

• binary tree의 i번째 row에 있는 노드의 수가 2^(i-1)개인 것은 아니다!

INPUT: root=[3,null,30,10,null,null,15,null,45]
OUTPUT: [3,30,10,15,45]

/**
 * 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) {}
 * };
 */

#include <algorithm>
#include <queue>
#include <limits>

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if(root == nullptr) return vector<int>();
        
        //array of max value in each row
        vector<int> answer = vector<int>();
        
        queue<TreeNode*> curRowQ;
        queue<TreeNode*> nextRowQ;

        curRowQ.push(root);
        int rowMax = INT_MIN;
        while(!curRowQ.empty()){
            TreeNode* curNode = curRowQ.front();
            curRowQ.pop();

            rowMax = max(rowMax, curNode->val);

            if(curNode->left != nullptr) nextRowQ.push(curNode->left);
            if(curNode->right != nullptr) nextRowQ.push(curNode->right);
           
            if(curRowQ.empty()){
                answer.push_back(rowMax);
                rowMax = INT_MIN;

                if(nextRowQ.empty()) break;

                curRowQ = nextRowQ;
                nextRowQ = queue<TreeNode*>();
           }
        }
        return answer;
    }
};