数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学判断给定二叉树的垂直层是否已排序 (C++)
概念
针对给定的二叉树，我们的任务是确定给定垂直层是否已排序。
（在这种情况下，当两个节点重叠时，请验证它们在其所在的层中是否形成排序序列。）
输入
2 / \ 3 6 / \ 8 5 / 7 Level l = -1
输出
Yes
-1 层的节点是 3 -> 7，它们形成一个排序序列。
输入
2 / \ 3 7 \ / 4 5 Level l = 0
输出
Yes
需要注意的是，值为 4 和 5 的节点在二叉树中重叠。
现在我们验证这是否按层形成排序序列。0 层的节点是 2 -> 4 -> 5，它们形成一个排序序列。
方法
根据简单的解决方案，首先我们执行二叉树的层序遍历，并将每个垂直层存储在不同的数组中。在这种情况下，我们验证与层 l 对应的数组是否已排序。需要注意的是，此解决方案的内存需求很大，可以减少。
根据高效的解决方案，我们执行二叉树的垂直层序遍历，并跟踪二叉树垂直层 l 中的节点值。如果前一个元素小于或等于当前元素，则会生成排序序列。在执行垂直层序遍历时，存储前一个值并将垂直层 l 中的当前节点与此层 l 的前一个值进行比较。可以看出，如果当前节点值大于或等于前一个值，则必须重复相同的过程，直到层 l 结束。可以看出，如果在任何阶段当前节点值小于前一个值，则层 l 未排序。再次观察到，如果我们到达层 l 的末尾，则该层已排序。
示例
// CPP program to determine whether
// vertical level l of binary tree
// is sorted or not.
#include <bits/stdc++.h>
using namespace std;
// Shows structure of a tree node.
struct Node1 {
int key1;
Node1 *left1, *right1;
};
// Shows function to create new tree node.
Node1* newNode(int key1){
Node1* temp1 = new Node1;
temp1->key1 = key1;
temp1->left1 = temp1->right1 = NULL;
return temp1;
}
// Indicates helper function to determine if
// vertical level l of given binary
// tree is sorted or not.
bool isSorted1(Node1* root1, int level1){
// So If root is null, then the answer is an
// empty subset and an empty subset is
// always considered to be sorted.
if (root1 == NULL)
return true;
// Indicates variable to store previous
// value in vertical level l.
int prevVal1 = INT_MIN;
// Indicates variable to store current level
// while traversing tree vertically.
int currLevel1;
// Indicates variable to store current node
// while traversing tree vertically.
Node1* currNode1;
// Used to declare queue to do vertical order
// traversal. A pair is used as element
// of queue. The first element in pair
// represents the node and the second
// element represents vertical level
// of that node.
queue<pair<Node1*, int>> q1;
// Used to insert root in queue. Vertical level
// of root is 0.
q1.push(make_pair(root1, 0));
// Perform vertical order traversal until
// all the nodes are not visited.
while (!q1.empty()) {
currNode1 = q1.front().first;
currLevel1 = q1.front().second;
q1.pop();
// Verify if level of node extracted from
// queue is required level or not. If it
// is the required level then verify if
// previous value in that level is less
// than or equal to value of node.
if (currLevel1 == level1) {
if (prevVal1 <= currNode1->key1)
prevVal1 = currNode1->key1;
else
return false;
}
// So if left child is not NULL then push it
// in queue with level reduced by 1.
if (currNode1->left1)
q1.push(make_pair(currNode1->left1, currLevel1 - 1));
// So if right child is not NULL then push it
// in queue with level increased by 1.
if (currNode1->right1)
q1.push(make_pair(currNode1->right1, currLevel1 + 1));
}
// So if the level asked is not present in the
// given binary tree, that means that level
// will contain an empty subset. Therefore answer
// will be true.
return true;
}
// Driver program
int main(){
/*
2
/ \
3 6
/ \
8 5
/
7
*/
Node1* root1 = newNode(2);
root1->left1 = newNode(3);
root1->right1 = newNode(6);
root1->left1->left1 = newNode(8);
root1->left1->right1 = newNode(5);
root1->left1->right1->left1 = newNode(7);
int level1 = -1;
if (isSorted1(root1, level1) == true)
cout << "Yes";
else
cout << "No";
return 0;
}输出
Yes
更新于：2020年7月24日
70 次浏览
广告