資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告