Dado un árbol binario. Encuentra si un nivel vertical dado del árbol binario está ordenado o no.
(En el caso de que dos Nodes se superpongan, verifique si forman una secuencia ordenada en el nivel en el que se encuentran).
Requisito previo: Transversal de orden vertical
Ejemplos:
C++
// CPP program to determine whether
// vertical level l of binary tree
// is sorted or not.
#include <bits/stdc++.h>
using namespace std;
// Structure of a tree node.
struct Node {
int key;
Node *left, *right;
};
// Function to create new tree node.
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
// Helper function to determine if
// vertical level l of given binary
// tree is sorted or not.
bool isSorted(Node* root, int level)
{
// If root is null, then the answer is an
// empty subset and an empty subset is
// always considered to be sorted.
if (root == NULL)
return true;
// Variable to store previous
// value in vertical level l.
int prevVal = INT_MIN;
// Variable to store current level
// while traversing tree vertically.
int currLevel;
// Variable to store current node
// while traversing tree vertically.
Node* currNode;
// 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<Node*, int> > q;
// Insert root in queue. Vertical level
// of root is 0.
q.push(make_pair(root, 0));
// Do vertical order traversal until
// all the nodes are not visited.
while (!q.empty()) {
currNode = q.front().first;
currLevel = q.front().second;
q.pop();
// Check if level of node extracted from
// queue is required level or not. If it
// is the required level then check if
// previous value in that level is less
// than or equal to value of node.
if (currLevel == level) {
if (prevVal <= currNode->key)
prevVal = currNode->key;
else
return false;
}
// If left child is not NULL then push it
// in queue with level reduced by 1.
if (currNode->left)
q.push(make_pair(currNode->left, currLevel - 1));
// If right child is not NULL then push it
// in queue with level increased by 1.
if (currNode->right)
q.push(make_pair(currNode->right, currLevel + 1));
}
// 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()
{
/*
1
/ \
2 5
/ \
7 4
/
6
*/
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(7);
root->left->right = newNode(4);
root->left->right->left = newNode(6);
int level = -1;
if (isSorted(root, level) == true)
cout << "Yes";
else
cout << "No";
return 0;
}
Python3
# Python program to determine whether
# vertical level l of binary tree
# is sorted or not.
from collections import deque
from sys import maxsize
INT_MIN = -maxsize
# Structure of a tree node.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# Helper function to determine if
# vertical level l of given binary
# tree is sorted or not.
def isSorted(root: Node, level: int) -> bool:
# If root is null, then the answer is an
# empty subset and an empty subset is
# always considered to be sorted.
if root is None:
return True
# Variable to store previous
# value in vertical level l.
prevVal = INT_MIN
# Variable to store current level
# while traversing tree vertically.
currLevel = 0
# Variable to store current node
# while traversing tree vertically.
currNode = Node(0)
# 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.
q = deque()
# Insert root in queue. Vertical level
# of root is 0.
q.append((root, 0))
# Do vertical order traversal until
# all the nodes are not visited.
while q:
currNode = q[0][0]
currLevel = q[0][1]
q.popleft()
# Check if level of node extracted from
# queue is required level or not. If it
# is the required level then check if
# previous value in that level is less
# than or equal to value of node.
if currLevel == level:
if prevVal <= currNode.key:
prevVal = currNode.key
else:
return False
# If left child is not NULL then push it
# in queue with level reduced by 1.
if currNode.left:
q.append((currNode.left, currLevel - 1))
# If right child is not NULL then push it
# in queue with level increased by 1.
if currNode.right:
q.append((currNode.right, currLevel + 1))
# 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 Code
if __name__ == "__main__":
# /*
# 1
# / \
# 2 5
# / \
# 7 4
# /
# 6
# */
root = Node(1)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(7)
root.left.right = Node(4)
root.left.right.left = Node(6)
level = -1
if isSorted(root, level):
print("Yes")
else:
print("No")
# This code is contributed by
# sanjeev2552
Javascript
<script>
// Javascript program to determine whether
// vertical level l of binary tree
// is sorted or not.
class Node
{
constructor(key)
{
this.left = null;
this.right = null;
this.key = key;
}
}
// Function to create new tree node.
function newNode(key)
{
let temp = new Node(key);
return temp;
}
// Helper function to determine if
// vertical level l of given binary
// tree is sorted or not.
function isSorted(root, level)
{
// If root is null, then the answer is an
// empty subset and an empty subset is
// always considered to be sorted.
if (root == null)
return true;
// Variable to store previous
// value in vertical level l.
let prevVal = Number.MIN_VALUE;
// Variable to store current level
// while traversing tree vertically.
let currLevel;
// Variable to store current node
// while traversing tree vertically.
let currNode;
// 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.
let q = [];
// Insert root in queue. Vertical level
// of root is 0.
q.push([root, 0]);
// Do vertical order traversal until
// all the nodes are not visited.
while (q.length > 0)
{
currNode = q[0][0];
currLevel = q[0][1];
q.shift();
// Check if level of node extracted from
// queue is required level or not. If it
// is the required level then check if
// previous value in that level is less
// than or equal to value of node.
if (currLevel == level)
{
if (prevVal <= currNode.key)
prevVal = currNode.key;
else
return false;
}
// If left child is not NULL then push it
// in queue with level reduced by 1.
if (currNode.left)
q.push([currNode.left, currLevel - 1]);
// If right child is not NULL then push it
// in queue with level increased by 1.
if (currNode.right)
q.push([currNode.right, currLevel + 1]);
}
// 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 code
/*
1
/ \
2 5
/ \
7 4
/
6
*/
let root = newNode(1);
root.left = newNode(2);
root.right = newNode(5);
root.left.left = newNode(7);
root.left.right = newNode(4);
root.left.right.left = newNode(6);
let level = -1;
if (isSorted(root, level) == true)
document.write("Yes");
else
document.write("No");
// This code is contributed by divyesh072019
</script>