檢查二叉樹是否在偶數層和奇數層分別包含嚴格遞增和遞減的節點值

---

二叉樹的層級 - 在二叉樹中，節點的層級是指它到根節點的距離。根節點位於第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是二叉樹中的節點數。它可以有效地確定二叉樹是否滿足所需條件，並且適用於實際應用。