[LeetCode] 1609. Even Odd Tree

https://leetcode.com/problems/even-odd-tree/description/

LeetCode - Even Odd Tree

문제 유형 : 이진트리

문제 난이도 : Medium

 

문제

A binary tree is named Even-Odd if it meets the following conditions:

• The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
• For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
• For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

 

이진 트리는 아래의 조건을 만족하면 Even-Odd트리라고 불린다.

• 이진 트리의 루트는 레벨 0이다. 자식노드는 레벨 1이고, 그들의 자식노드는 레벨 2이다. 이러한 식으로 레벨이 진행된다.
• 짝수 레벨의 노드의 값은 왼쪽에서 오른쪽으로 엄격한 오름차순이어야 하고, 홀수여야 한다.
• 홀수 레벨의 노드의 값은 왼쪽에서 오른쪽으로 엄격한 내림차순이어야 하고, 짝수여야 한다.

이진 트리의 루트가 주어진다. 이진 트리다 Even-Odd라고 불리는지 확인하고, 아니면 false를 반환하시오.

 

풀이

너비 우선 탐색을 이용하여 문제를 해결했다.

처음에 큐의 크기를 잰 다음, 그 크기만큼만 순회하면 레벨별로 구분해서 순회할 수 있다.

탐색하면서 트리의 조건을 깨는 게 있다면 false를 반환하고, 무사히 순회를 마치면 true를 반환한다.

 

코드

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) {}
 * };
 */
#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        queue<TreeNode*> q;
        bool even = true;
        q.push(root);

        while(!q.empty()) {
            int qSize = q.size();
            int prev = even? -1 : 1e9;

            for(int i = 0; i < qSize; i++) {
                auto curr = q.front() ;
                q.pop();

                if(even) {
                    if(curr -> val % 2 == 0) return false;
                    if(curr -> val <= prev) return false;
                    prev = curr -> val;
                } else {
                    if(curr -> val % 2 == 1) return false;
                    if(curr -> val >= prev) return false;
                    prev = curr -> val;
                }

                if(curr -> left) {
                    q.push(curr -> left);
                }

                if(curr -> right) {
                    q.push(curr -> right);
                }
            }
            even = !even;
        }
        return true;
    }
};