数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究检查二叉树是否为奇偶树
奇偶树 − 如果所有偶数层（将根节点视为第 0 层）的节点都具有偶数值，并且所有奇数层的节点都具有奇数值，则二叉树称为奇偶树。
问题陈述
给定一棵二叉树。任务是检查二叉树是否为奇偶树。
示例 1
输入
6
/ \
3 7
/ \
2 8
/ \ /
11 3 9
输出
True
解释
第 0 层（偶数）= 节点值为 6 -> 偶数
第 1 层（奇数）= 节点值为 3 -> 奇数 和 7 -> 奇数
第 2 层（偶数）= 节点值为 2 -> 偶数 和 8 -> 偶数
第 3 层（奇数）= 节点值为 11 -> 奇数，3 -> 奇数 和 9 -> 奇数
因此，给定的树是奇偶树。
示例 2
输入
5
/ \
4 7
/
2
输出
False
解释
第 0 层（偶数）= 节点值为 5 -> 奇数 - 错误
第 1 层（奇数）= 节点值为 4 -> 偶数 和 7 -> 奇数 - 错误
第 2 层（偶数）= 节点值为 2 -> 偶数
因此，给定的树不是奇偶树。
方法 1：深度优先搜索 (DFS) 方法
该问题的 DFS 解决方案是在树的每个搜索层检查节点值。如果所有节点的节点值和层级都是偶数或都是奇数，则返回 true，否则返回 false。
伪代码
isEvenOddTree(node, level):
if node is null:
return true
# Check if the node's value is valid for its level
if level is even:
if node.value is not even:
return false
else:
if node.value is not odd:
return false
# Recursively check the left and right subtrees
leftResult = isEvenOddTree(node.left, level + 1)
rightResult = isEvenOddTree(node.right, level + 1)
return leftResult and rightResult
isEvenOddTree(root):
return isEvenOddTree(root, 0)
示例：C++ 实现
以下是所提出的 DFS 解决方案的 C++ 实现。
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};
bool is_even_odd_tree_helper(TreeNode* node, int level){
if (!node) {
return true;
}
// Check if the node's value is valid for its level
if (level % 2 == 0) { // Even level
if (node->val % 2 != 0) {
return false;
}
} else { // Odd level
if (node->val % 2 == 0) {
return false;
}
}
// Recursively check the left and right subtrees
return is_even_odd_tree_helper(node->left, level + 1) &&
is_even_odd_tree_helper(node->right, level + 1);
}
bool is_even_odd_tree(TreeNode* root){
return is_even_odd_tree_helper(root, 0);
}
int main(){
// Test case:
// 4
// / \
// 3 7
// / \ \
// 4 6 2
TreeNode* root = new TreeNode(4);
root->left = new TreeNode(3);
root->right = new TreeNode(7);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(6);
root->right->right = new TreeNode(2);
if (is_even_odd_tree(root)) {
std::cout << "The tree is an Even-Odd Tree.\n";
} else {
std::cout << "The tree is NOT an Even-Odd Tree.\n";
}
// Clean up memory
delete root->left->left;
delete root->left->right;
delete root->right->left;
delete root->right->right;
delete root->left;
delete root->right;
delete root;
return 0;
}
输出
The tree is an Even-Odd Tree.
时间复杂度 − O(N)，其中 N 是二叉树中的节点数。
空间复杂度 − O(N)，其中 N 是二叉树中的节点数。
方法 2：广度优先搜索 (BFS) 方法
该问题的 BFS 解决方案是在树的每个搜索层检查节点值。如果所有节点的节点值和层级都是偶数或都是奇数，则返回 true，否则返回 false。
伪代码 −
function is_even_odd_tree(root):
if root is null:
return true
queue = Queue()
queue.push(root)
is_even_level = true
while queue is not empty:
level_size = queue.size()
prev_val = INT_MIN if is_even_level else INT_MAX
for i from 0 to level_size - 1:
node = queue.front()
queue.pop()
// Check if the node's value is valid for its level
if is_even_level: // Even level
if node.val is odd:
return false
else: // Odd level
if node.val is even:
return false
prev_val = node.val
if node.left is not null:
queue.push(node.left)
if node.right is not null:
queue.push(node.right)
is_even_level = not is_even_level
return true
示例：C++ 实现
以下是所提出的 BFS 解决方案的 C++ 实现。
#include <iostream>
#include <queue>
#include <climits>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};
bool is_even_odd_tree(TreeNode* root){
if (!root) {
return true;
}
std::queue<TreeNode*> q;
q.push(root);
bool is_even_level = true;
while (!q.empty()) {
int level_size = q.size();
int prev_val = is_even_level ? INT_MIN : INT_MAX;
for (int i = 0; i < level_size; ++i) {
TreeNode* node = q.front();
q.pop();
// Check if the node's value is valid for its level
if (is_even_level) { // Even level
if (node->val % 2 != 0) {
return false;
}
} else { // Odd level
if (node->val % 2 == 0) {
return false;
}
}
prev_val = node->val;
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
is_even_level = !is_even_level;
}
return true;
}
int main(){
// Test case:
// 4
// / \
// 3 7
// / \ / \
// 2 8 8 21
TreeNode* root = new TreeNode(4);
root->left = new TreeNode(3);
root->right = new TreeNode(7);
root->left->left = new TreeNode(2);
root->left->right = new TreeNode(8);
root->right->left = new TreeNode(8);
root->right->right = new TreeNode(21);
if (is_even_odd_tree(root)) {
std::cout << "The tree is an Even-Odd Tree.\n";
} else {
std::cout << "The tree is NOT an Even-Odd Tree.\n";
}
// Clean up memory
delete root->left->left;
delete root->left->right;
delete root->right->left;
delete root->right->right;
delete root->left;
delete root->right;
delete root;
return 0;
}
输出
The tree is NOT an Even-Odd Tree.
时间复杂度 − O(N)，N 是二叉树中的节点数。
空间复杂度 − O(w)，w 是节点数最多的层中的节点数。
结论
总之，为了确定二叉树是否为奇偶树，我们可以执行两种类型的遍历，即深度优先搜索和广度优先搜索，它们具有相同的时间复杂度。
更新于： 2023-10-25
141 次查看
广告