检查给定树的左视图是否已排序
在这个问题中，我们将检查二叉树的左视图是否已排序。
二叉树的左视图是指从左侧查看二叉树时可以看到的节点。简单来说，我们只能看到每个级别的第一个节点。因此，我们需要提取第一个节点的值并检查它们是否已排序以获取输出。
问题陈述
我们给出了一个二叉树。我们需要打印二叉树的左视图是否已排序。如果已排序，则打印"是"。否则，在输出中打印"否"。
示例
输入
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' 变量。同时，使用 -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;
// 二叉树节点
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;
// 跟踪左视图是否已排序
bool isSorted = true;
que.push(head);
int p = -1, q = -1;
// BFS 算法
while (!que.empty()) {
int len = que.size();
// 遍历各级节点
while (len > 0) {
head = que.front();
// 初始级别的变量
if (p == -1) {
q = head->data;
}
// 检查左视图是否排序的逻辑
if (p == -2) {
if (q <= head->data) {
q = head->data;
p = -3;
} else {
isSorted = false;
break;
}
}
// 将左子节点插入队列
if (head->left != NULL) {
que.push(head->left);
}
// 将右子节点插入队列
if (head->right != NULL) {
que.push(head->right);
}
len = len - 1;
que.pop();
}
p = -2;
// 当值未排序时
if (isSorted == false) {
break;
}
}
if (isSorted)
cout << "是的，树的左视图已排序!" << endl;
else
cout << "否，树的左视图未排序!" << 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;
}
输出
是的，树的左视图已排序!
时间复杂度 − O(N)，因为我们遍历树的每个节点。
空间复杂度 − O(N)，因为我们将树的每个节点存储在队列中。
结论
在这里，我们学会了检查树的左视图是否按升序排序。但是，程序员也可以检查左视图是否按降序排序。要检查树的右视图是否缩短，程序员应该比较每个级别的最后一个节点。
