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

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

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

问题描述

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

示例示例

输入

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 - 定义名为queue的’que’来存储树节点。还要将头节点插入队列中。

• 步骤3 - 用true布尔值初始化’isSorted’变量。还要用-1初始化p和q。

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

结论

在这里，我们学会了检查树的左视图是否以递增顺序排序。但是，程序员还可以检查左视图是否以递减顺序排序。要检查树的右视图是否缩短，程序员应该比较每个级别的最后一个节点。