Re: [閒聊] 每日leetcode
看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間2月前 (2024/02/29 22:35)推噓0(0推 0噓 0→)留言0則, 0人參與討論串9/231 (看更多)
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;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.172.109 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1709217312.A.101.html
※ 編輯: DJYOSHITAKA (114.137.172.109 臺灣), 02/29/2024 22:35:30
討論串 (同標題文章)