检查二叉树是否在偶数层和奇数层分别包含严格递增和递减的节点值

---

二叉树的层级 - 在二叉树中，节点的层级是指它到根节点的距离。根节点位于第0层，它的直接子节点位于第1层，它们的子节点位于第2层，以此类推。

以下示例解释了二叉树的层级：

        A           <- Level 0
      /   \
     B     C        <- Level 1
    / \   / \
   D   E F   G      <- Level 2

问题陈述

给定一棵二叉树，检查它是否在偶数层和奇数层分别包含严格递增和递减的节点值。

示例1

输入

         2
      /     \
     9        7
    / \     /  \
   1   5   6    8

输出

True

解释

第1层 - 节点值9和7严格递减

第2层 - 节点值1、5、6和8严格递增

因此，给定的树在偶数层和奇数层分别具有严格递增和递减的节点值。

示例2

输入

        8
      /   \
     9     8
    / \
   4   3

输出

False

解释

第1层 - 节点值9和8严格递减

第2层 - 节点值4和3不是严格递增的

因此，给定的树在偶数层和奇数层分别具有严格递增和递减的节点值。

解决方案

使用队列执行二叉树的层序遍历，队列最初包含根节点。随着函数的遍历，从第0层开始跟踪树的层级。在每一层，节点值存储在一个向量中，以检查它们是严格递增、严格递减还是都不是。然后检查节点的层级。如果节点层级为偶数且节点值严格递增，或者层级为奇数且节点值严格递减，则返回True，否则返回False。

伪代码 -

function checkEvenOddLevel(root):
   if root is NULL:
      return true    
   queue = empty queue
   enqueue root to queue
   level = 0    
   while queue is not empty:
      vec = empty vector        
      size = size of queue
        
      for i = 0 to size - 1:
         node = dequeue from queue
         add node's value to vec            
         if node has left child:
            enqueue left child to queue            
         if node has right child:
            enqueue right child to queue        
      if level is even:
         for i = 0 to size of vec - 2:
            if vec[i + 1] <= vec[i]:
               return false        
      if level is odd:
         for i = 0 to size of vec - 2:
            if vec[i + 1] >= vec[i]:
               return false        
      increment level by 1    
   return true
root = create binary tree
if checkEvenOddLevel(root):
   print "True"
else:
   print "False"

示例：C++ 实现

以下代码检查二叉树的偶数层和奇数层节点值是否严格递增或递减。

// C++ program for the above approach
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Node {
   int val;
   Node* left, *right;
};
Node* newNode(int data) {
   Node* temp = new Node();
   temp->val = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
// Function to check if given binary tree satisfies the required conditions
bool checkEvenOddLevel(Node* root) {
   if (root == NULL)
      return true;
   // Queue to store nodes of each level
   queue<Node*> q;
   q.push(root);
   // Stores the current level of the binary tree
   int level = 0;
   // Traverse until the queue is empty
   while (!q.empty()) {
      vector<int> vec;
      // Stores the number of nodes present in the current level
      int size = q.size();
      for (int i = 0; i < size; i++) {
         Node* node = q.front();
         vec.push_back(node->val);
         // Insert left and right child of node into the queue
         if (node->left != NULL)
            q.push(node->left);
         if (node->right != NULL)
            q.push(node->right);
         q.pop();
      }
      // If the level is even
      if (level % 2 == 0) {
         // If the nodes in this level are in strictly increasing order or not
         for (int i = 0; i < vec.size() - 1; i++) {
            if (vec[i + 1] > vec[i])
               continue;
            return false;
         }
      }
      // If the level is odd
      else if (level % 2 == 1) {
         // If the nodes in this level are in strictly decreasing order or not
         for (int i = 0; i < vec.size() - 1; i++) {
            if (vec[i + 1] < vec[i])
               continue;
            return false;
         }
      }
      // Increment the level count
      level++;
   }
   return true;
}
int main(){
   // Construct a Binary Tree
   Node* root = NULL;
   root = newNode(2);
   root->left = newNode(6);
   root->right = newNode(3);
   root->left->left = newNode(4);
   root->left->right = newNode(7);
   root->right->right = newNode(11);
   root->left->left->left = newNode(10);
   root->left->left->right = newNode(5);
   root->left->right->right = newNode(1);
   // Function Call
   if (checkEvenOddLevel(root))
      cout << "True";
   else
      cout << "False";
   return 0;
}

输出

True

时间复杂度 - O(n)，因为我们遍历了整棵树一次

空间复杂度 - O(n)，因为队列和向量使用了空间。

结论

在讨论中，我们讨论了检查二叉树是否在偶数层和奇数层分别包含严格递增和递减的节点值的问题。它使用队列执行层序遍历，并根据层级是偶数还是奇数检查每一层的数值顺序。该代码的时间复杂度为O(N)，空间复杂度为O(N)，其中N是二叉树中的节点数。它可以有效地确定二叉树是否满足所需条件，并且适用于实际应用。