LeetCode-Solution/LeetCode1609.cpp at main · nfpranta/LeetCode-Solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 *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:
    bool isEvenOddTree(TreeNode *root)
    {
        int level = 0;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty())
        {
            int sz = q.size();
            int prev_val;
            if (level % 2 == 0)
            {
                prev_val = INT_MIN;
            }
            else
                prev_val = INT_MAX;
            for (int i = 0; i < sz; i++)
            {
                TreeNode *node = q.front();
                q.pop();
                if (level % 2 == 0 and (node->val % 2 == 0 or prev_val >= node->val))
                    return false;
                else if (level % 2 == 1 and (node->val % 2 == 1 or prev_val <= node->val))
                    return false;
                prev_val = node->val;
                if (node->left)
                {
                    q.push(node->left);
                }
                if (node->right)
                {
                    q.push(node->right);
                }
            }
            level++;
        }
        return true;
    }
};