查找是否在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的该先前值进行比较。已经看到,如果当前节点值大于或等于先前值,则我们必须重复相同的过程,直到级别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
猜你喜欢