检查二叉树是否为奇偶树

奇偶树 − 如果所有偶数层（将根节点视为第 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++ 实现。

Open Compiler
#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 是二叉树中的节点数。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

方法 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++ 实现。

Open Compiler
#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 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告