1609. Even Odd Tree
BFS
一開始送出去沒注意到cur_level != pre_level的時候也要確認奇偶
(不然會少確認到每個level最左的那顆) 就錯惹
剩下就是一堆if
bool isEvenOddTree(TreeNode* root) {
queue<pair<TreeNode*,int>> q;
q.push({root, 0});
int pre_level = 0;
int pre_value = -1;
while(!q.empty())
{
TreeNode* n = q.front().first;
int level = q.front().second;
int cur_val = n->val;
q.pop();
if(level == pre_level)
{
// at same level
if(level%2 == 0 && (pre_value >= cur_val || cur_val%2 == 0))
{
return false;
}
else if(level%2 == 1 && (pre_value <= cur_val || cur_val%2 == 1))
{
return false;
}
else
{
pre_value = cur_val;
}
}
else
{
// to next level, also need to check
if((level%2 == 0 && cur_val%2 == 0) || (level%2 == 1 && cur_val%2
== 1))
{
return false;
}
pre_level = level;
pre_value = cur_val;
}
if(n->left) {q.push({n->left, level+1});}
if(n->right) {q.push({n->right, level+1});}
}
return true;
}