1609.奇偶数

目录

一、题目

二、代码

三、完整测试代码

一、题目

1609. 奇偶树 - 力扣（LeetCode）

二、代码

/*** 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 LevelOrder(TreeNode* root)//层序遍历
{deque<TreeNode*> q;if (root == nullptr){return false;}q.push_back(root);int level = 0;//层次while (!q.empty())//循环进队{int n = q.size();int mark = level % 2 == 0 ? INT_MIN : INT_MAX;while (n--){TreeNode* front = q.front();q.pop_front();if (front != nullptr){if (level % 2 == 0)//偶数层{if (front->val % 2 == 0)//节点的值不是奇数{return false;}else//节点的值是奇数{if (mark < front->val){mark = front->val;}else{return false;}}}else//奇数层{if (front->val % 2 != 0)//不是偶数{return false;}else{if (mark > front->val){mark = front->val;}else {return false;}}}q.push_back(front->left);q.push_back(front->right);}}level++;}return true;
}bool isEvenOddTree(TreeNode * root){return LevelOrder(root);}};

三、完整测试代码

#include<iostream>
#include<deque>
using namespace std;
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};bool LevelOrder(TreeNode* root)//层序遍历
{deque<TreeNode*> q;if (root == nullptr){return false;}q.push_back(root);int level = 0;//层次while (!q.empty())//循环进队{int n = q.size();int mark = level % 2 == 0 ? INT_MIN : INT_MAX;//标记while (n--){TreeNode* front = q.front();q.pop_front();if (front != nullptr){if (level % 2 == 0)//偶数层{if (front->val % 2 == 0)//节点的值不是奇数{return false;}else//节点的值是奇数{if (mark < front->val){mark = front->val;}else{return false;}}}else//奇数层{if (front->val % 2 != 0)//不是偶数{return false;}else{if (mark > front->val){mark = front->val;}else {return false;}}}q.push_back(front->left);q.push_back(front->right);}}level++;}return true;
}bool isEvenOddTree(TreeNode* root)
{return LevelOrder(root);
}int main()
{TreeNode* root = new TreeNode(1);TreeNode* Node1 = new TreeNode(10);TreeNode* Node2 = new TreeNode(4);TreeNode* Node3 = new TreeNode(7);root->left = Node1;root->right = Node2;Node1->left = Node3;Node1->right = nullptr;Node2->left = nullptr;Node2->right = nullptr;Node3->left = nullptr;Node3->right = nullptr;int i = 0;cout << isEvenOddTree(root);return 0;
}