检查给定树的左视图是否已排序

---

在这个问题中，我们将检查二叉树的左视图是否已排序。

二叉树的左视图是指从二叉树左侧看到的节点。简单来说，我们只能看到每一层的第一个节点。因此，我们需要提取第一个节点的值，并检查它们是否已排序以获得输出。

问题陈述

我们给定一个二叉树。我们需要打印二叉树的左视图是否已排序。如果已排序，则打印“是”。否则，在输出中打印“否”。

示例

输入

  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)，因为我们将树的每个节点存储在队列中。

结论

在这里，我们学习了如何检查树的左视图是否按递增顺序排序。但是，程序员也可以检查左视图是否按递减顺序排序。要检查树的右视图是否已排序，程序员应该比较每一层的最后一个节点。