对于给定的二叉树,我们的任务是确定二叉树的给定垂直级别是否已排序。
(对于这种情况,当两个节点重叠时,请验证它们是否在它们所在的层次上形成排序的序列。)
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的该先前值进行比较。已经看到,如果当前节点值大于或等于先前值,则我们必须重复相同的过程,直到级别1结束。可以看出,如果在任何阶段,当前节点的值都小于先前的值,则不会对级别l进行排序。再次观察到,如果我们到达级别l的末尾,则会对级别进行排序。
// CPP program to determine whether //二叉树的垂直级别l- //是否排序。 #include <bits/stdc++.h> using namespace std; //显示树节点的结构。 struct Node1 { int key1; Node1 *left1, *right1; }; //显示创建新树节点的功能。 Node1* newNode(int key1){ Node1* temp1 = new Node1; temp1->key1 = key1; temp1->left1 = temp1->right1 = NULL; return temp1; } //指示辅助函数以确定是否 //给定二进制文件的垂直级别l- // tree是否排序。 bool isSorted1(Node1* root1, int level1){ //因此,如果root为null,则答案为 //空子集,而空子集是 //始终被视为已排序。 if (root1 == NULL) return true; //指示变量以存储上一个 //垂直水平l中的值。 int prevVal1 = INT_MIN; //指示变量以存储当前级别 //垂直穿过树时。 int currLevel1; //表示存储当前节点的变量 //垂直穿过树时。 Node1* currNode1; //用来声明队列做垂直顺序 //遍历。一对用作元素 //的队列。配对中的第一个元素 //代表节点,第二个 //元素代表垂直高度 //该节点的。 queue<pair<Node1*, int>> q1; //用于在队列中插入根。垂直水平 //的根为0。- q1.push(make_pair(root1, 0)); //执行垂直顺序遍历,直到 //所有节点均未访问。 while (!q1.empty()) { currNode1 = q1.front().first; currLevel1 = q1.front().second; q1.pop(); //提取节点的级别 //队列是否为必需级别。如果 //是必需的级别,然后验证是否 //该级别中的先前值较小 //等于或等于节点的值。 if (currLevel1 == level1) { if (prevVal1 <= currNode1->key1) prevVal1 = currNode1->key1; else return false; } //因此,如果左孩子不为NULL,则将其推送 //在队列中,级别降低1 if (currNode1->left1) q1.push(make_pair(currNode1->left1, currLevel1 - 1)); //因此,如果正确的子代不为NULL,则推送它 //队列中级别提高1 if (currNode1->right1) q1.push(make_pair(currNode1->right1, currLevel1 + 1)); } //因此,如果要求的级别不在 //给定二叉树,这意味着该级别 //将包含一个空子集。因此,答案 //会是真的。 return true; } //驱动程序 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