檢查給定樹的左檢視是否已排序

---

在這個問題中，我們將檢查二叉樹的左檢視是否已排序。

二叉樹的左檢視是指從二叉樹左側看到的節點。簡單來說，我們只能看到每一層的第一個節點。因此，我們需要提取第一個節點的值，並檢查它們是否已排序以獲得輸出。

問題陳述

我們給定一個二叉樹。我們需要列印二叉樹的左檢視是否已排序。如果已排序，則列印“是”。否則，在輸出中列印“否”。

示例

輸入

  9
 /  \
13   2

輸出

Yes

解釋

二叉樹的左檢視為 [9, 13]，按遞增順序排序。

輸入

      5
    /   \
   20    10
  /  \  /   \
25  10 5    42

輸出

Yes

解釋

樹的左檢視為 [5, 20, 25]。

輸入

 5
  \
   10
  /   \
 5    42

輸出

No

解釋

樹的左檢視為 [5, 10, 5]。

方法

在這種方法中，我們將使用層序遍歷演算法遍歷每一層二叉樹。我們將把每一層的每個節點儲存在佇列中。佇列的第一個節點是當前層的左節點，我們將檢查當前層的左節點是否大於前一層的左節點。

演算法

• 步驟 1 − 定義 TreeNode，表示樹的結構。此外，定義 createNewNode() 函式以建立一個二叉樹的新節點，並使用樹節點構造二叉樹。

• 步驟 2 − 定義名為“que”的佇列來儲存樹節點。此外，將頭節點插入佇列。

• 步驟 3 − 使用 true 布林值初始化 'isSorted' 變數。此外，將 p 和 q 初始化為 -1。

• 步驟 4 − 遍歷佇列，直到它為空。

• 步驟 5 − 使用巢狀迴圈遍歷每個佇列元素。

• 步驟 5.1 − 從佇列中移除第一個元素。如果 p 為 -1，則將元素的資料儲存在 q 中。

• 步驟 5.2 − 如果 p 為 -2，並且 q 小於當前節點的資料，則使用當前節點的資料更新 q，並使用 -3 更新 p。否則，將 isSorted 更新為 false 並中斷迴圈。

  這裡 p = -1 表示樹的第一個節點。如果 p 為 -2，則表示當前節點是當前層的第一個節點。如果 p 為 -3，則當前節點不是當前層的第一個節點。因此，我們不需要檢查它。

• 步驟 5.3 − 如果當前節點的左子節點和右子節點存在，則將它們插入佇列。此外，將佇列的長度減 1，並移除第一個節點。

• 步驟 6 − 將 p 更新為 -2。

• 步驟 7 − 如果在外部迴圈中 isSorted 為 false，則中斷迴圈。

• 步驟 8 − 最後，根據 'isSorted' 布林值列印答案。

示例

#include <bits/stdc++.h>
using namespace std;

// Binary Tree Node
struct TreeNode {
   int data;
   struct TreeNode *right, *left;
};
struct TreeNode *createNewNode(int key) {
   struct TreeNode *temp = new TreeNode;
   temp->data = key;
   temp->right = NULL;
   temp->left = NULL;
   return temp;
}
void CheckIfLeftSorted(TreeNode *head) {
   queue<TreeNode *> que;
   // To track whether the left view is sorted
   bool isSorted = true;
   que.push(head);
   int p = -1, q = -1;
   // BFS algorithm
   while (!que.empty()) {
      int len = que.size();
      // Traverse each level nodes
      while (len > 0) {
         head = que.front();
         // variable for initial level
         if (p == -1) {
            q = head->data;
         }
         // Logic to check whether the left view is sorted
         if (p == -2) {
            if (q <= head->data) {
               q = head->data;
               p = -3;
            } else {
               isSorted = false;
               break;
            }
         }
         // Insert the left child node in the queue
         if (head->left != NULL) {
            que.push(head->left);
         }
         // Insert the right child node in the queue
         if (head->right != NULL) {
            que.push(head->right);
         }
         len = len - 1;
         que.pop();
      }
      p = -2;
      // When the value is not sorted
      if (isSorted == false) {
         break;
      }
   }
   if (isSorted)
      cout << "Yes, the left view of the tree is sorted!" << endl;
   else
      cout << "No, the left view of the tree is not sorted!" << endl;
}
int main() {
   struct TreeNode *head = createNewNode(5);
   head->left = createNewNode(20);
   head->left->left = createNewNode(25);
   head->right = createNewNode(10);
   head->right->left = createNewNode(5);
   head->right->right = createNewNode(42);
   head->left->right = createNewNode(10);
   CheckIfLeftSorted(head);
   return 0;
}

輸出

Yes, the left view of the tree is sorted!

• 時間複雜度 − O(N)，因為我們遍歷樹的每個節點。

• 空間複雜度 − O(N)，因為我們將樹的每個節點儲存在佇列中。

結論

在這裡，我們學習瞭如何檢查樹的左檢視是否按遞增順序排序。但是，程式設計師也可以檢查左檢視是否按遞減順序排序。要檢查樹的右檢視是否已排序，程式設計師應該比較每一層的最後一個節點。