Dada la raíz de un árbol binario en el que todos los Nodes tienen valores de 0 o 1 , la tarea es verificar si el equivalente decimal nivelado del árbol dado forma una secuencia monótona o no.
Una sucesión es monótona si es monótona creciente o monótona decreciente.
Una secuencia nums es monótona creciente si para todo i <= j, nums[i] <= nums[j].
Una secuencia nums es monótona decreciente si para todo i <= j, nums[i] >= nums[j].
Ejemplos :
Entrada :
0
/ \
0 1
//
1 0
/ \
1 1
Salida :
Sí
Explicación :
Nivel 0: 0 -> 0
Nivel 1: 01 -> 1
Nivel 2: 10 -> 2
Nivel 3: 11 -> 3
La secuencia formado a partir del equivalente decimal de cada nivel desde la raíz hasta la hoja es {0, 1, 2, 3}, que es una secuencia creciente monótona.
Entrada :
1
/ \
1 1
/ /
1 0
/ \
0 1
Salida :
No
Acercarse:
La idea es realizar un recorrido por orden de niveles de un árbol determinado y, para cada nivel, convertir la representación binaria a decimal y almacenarla en una variable int. Luego, el problema se convertirá para simplemente verificar si la array dada es una secuencia monótona o no .
Siga los pasos a continuación para resolver este problema:
- Hacer un recorrido de orden de nivel desde la raíz hasta la hoja
- Para cada nivel, conviértalo a equivalente decimal y almacene el valor en una array de enteros
- Luego verifique si la array dada es monotónica creciente o decreciente
A continuación se muestra la implementación del enfoque anterior:
C#
// C# code to check if the tree is monotonic
using System;
using System.Collections.Generic;
using System.Linq;
// Class containing left and right
// child of current node and key value
public class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class GFG {
// Root of the Binary Tree
public Node root;
public virtual bool checkMonotonic(Node root)
{
int[] sequenceArray = getLevelOrderArray(root);
bool increasing = true;
bool decreasing = true;
for (int i = 0; i < sequenceArray.Length - 1; ++i) {
if (sequenceArray[i] > sequenceArray[i + 1])
increasing = false;
if (sequenceArray[i] < sequenceArray[i + 1])
decreasing = false;
}
return increasing || decreasing;
}
public virtual int[] getLevelOrderArray(Node root)
{
int h = height(root);
int i;
List<int> retVal = new List<int>();
for (i = 1; i <= h; i++) {
List<int> currentLevel = new List<int>();
var currentLevelOrder
= getCurrentLevel(root, i, currentLevel)
.ToList();
retVal.Add(Convert.ToInt32(
string.Join("", currentLevelOrder), 2));
}
return retVal.ToArray();
}
// Compute the "height" of a tree --
// the number of nodes along the longest
// path from the root node down to the
// farthest leaf node.
public virtual int height(Node root)
{
if (root == null) {
return 0;
}
else {
// compute height of each subtree
int lheight = height(root.left);
int rheight = height(root.right);
// use the larger one
if (lheight > rheight) {
return (lheight + 1);
}
else {
return (rheight + 1);
}
}
}
// Get nodes at the current level
public virtual IList<int>
getCurrentLevel(Node root, int level,
List<int> currentLevelOrder)
{
if (root == null) {
return currentLevelOrder;
}
if (level == 1) {
currentLevelOrder.Add(root.data);
}
else if (level > 1) {
getCurrentLevel(root.left, level - 1,
currentLevelOrder);
getCurrentLevel(root.right, level - 1,
currentLevelOrder);
}
return currentLevelOrder;
}
// Driver Code
public static void Main(string[] args)
{
GFG tree = new GFG();
tree.root = new Node(0);
tree.root.left = new Node(0);
tree.root.right = new Node(1);
tree.root.left.left = new Node(1);
tree.root.right.left = new Node(0);
tree.root.right.left.left = new Node(1);
tree.root.right.left.right = new Node(1);
bool ans = tree.checkMonotonic(tree.root);
if (ans)
Console.Write("Yes");
else
Console.Write("No");
}
}
Yes
Complejidad de tiempo : O(N^2)
Espacio auxiliar : O(N+L), donde L es el conteo de niveles en Tree, que tendrá el tamaño de Array para almacenar el valor decimal de cada nivel
Enfoque eficiente: el espacio auxiliar en el enfoque anterior se puede optimizar simplemente mirando los niveles adyacentes y verificando si siguen una secuencia monótona o no.
En lugar de almacenar el equivalente decimal de cada nivel en una array y luego verificar si la array es monótona, podemos verificar la naturaleza creciente/decreciente de cada nivel a medida que lo recorremos. De esta manera, podemos terminar tan pronto como obtengamos un valor que rompa la monotonicidad. Para que esto funcione, necesitaremos almacenar el valor del nivel anterior para compararlo con el siguiente nivel.
A continuación se muestra la implementación del enfoque anterior:
C#
// C# code to implement the above approach
using System;
using System.Collections.Generic;
using System.Linq;
// Class containing left and right
// child of current node and key value
public class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class GFG {
// Root of the Binary Tree
public Node root;
public virtual bool checkMonotonic(Node root)
{
int h = height(root);
int i;
int prevLevelValue
= Convert.ToInt32(root.data.ToString(), 2);
bool increasing = true;
bool decreasing = true;
for (i = 1; i <= h; i++) {
List<int> currentLevel = new List<int>();
var currentLevelOrder
= getCurrentLevel(root, i, currentLevel)
.ToList();
int currentLevelValue = Convert.ToInt32(
string.Join("", currentLevelOrder), 2);
if (prevLevelValue > currentLevelValue)
increasing = false;
if (prevLevelValue < currentLevelValue)
decreasing = false;
prevLevelValue = currentLevelValue;
}
return increasing || decreasing;
}
// Compute the "height" of a tree --
// the number of nodes along the longest
// path from the root node down to the
// farthest leaf node.
public virtual int height(Node root)
{
if (root == null) {
return 0;
}
else {
// compute height of each subtree
int lheight = height(root.left);
int rheight = height(root.right);
/* use the larger one */
if (lheight > rheight) {
return (lheight + 1);
}
else {
return (rheight + 1);
}
}
}
// Get nodes at the current level
public virtual IList<int>
getCurrentLevel(Node root, int level,
List<int> currentLevelOrder)
{
if (root == null) {
return currentLevelOrder;
}
if (level == 1) {
currentLevelOrder.Add(root.data);
}
else if (level > 1) {
getCurrentLevel(root.left, level - 1,
currentLevelOrder);
getCurrentLevel(root.right, level - 1,
currentLevelOrder);
}
return currentLevelOrder;
}
// Driver Code
public static void Main(string[] args)
{
GFG tree = new GFG();
tree.root = new Node(0);
tree.root.left = new Node(0);
tree.root.right = new Node(1);
tree.root.left.left = new Node(1);
tree.root.right.left = new Node(0);
tree.root.right.left.left = new Node(1);
tree.root.right.left.right = new Node(1);
bool ans = tree.checkMonotonic(tree.root);
if (ans)
Console.Write("Yes");
else
Console.Write("No");
}
}
Yes
Complejidad de tiempo : O(N^2)
Espacio auxiliar : O(N)