数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学检查给定树的左视图是否已排序
在这个问题中，我们将检查二叉树的左视图是否已排序。
二叉树的左视图是指从二叉树左侧看到的节点。简单来说，我们只能看到每一层的第一个节点。因此，我们需要提取第一个节点的值，并检查它们是否已排序以获得输出。
问题陈述
我们给定一个二叉树。我们需要打印二叉树的左视图是否已排序。如果已排序，则打印“是”。否则，在输出中打印“否”。
示例
输入
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]。
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
方法
在这种方法中，我们将使用层序遍历算法遍历每一层二叉树。我们将把每一层的每个节点存储在队列中。队列的第一个节点是当前层的左节点，我们将检查当前层的左节点是否大于前一层的左节点。
算法
步骤 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)，因为我们将树的每个节点存储在队列中。
结论
在这里，我们学习了如何检查树的左视图是否按递增顺序排序。但是，程序员也可以检查左视图是否按递减顺序排序。要检查树的右视图是否已排序，程序员应该比较每一层的最后一个节点。
85 次浏览
