Dado un árbol , nuestra tarea es verificar si su vista izquierda está ordenada o no. Si es así, devuelve verdadero ; de lo contrario , es falso.
Ejemplos:
Aporte:
Salida: verdadero
Explicación:
La vista izquierda del árbol sería 10, 20, 50, que está ordenada.
Enfoque:
Para resolver el problema mencionado anteriormente, tenemos que realizar un recorrido de orden de nivel en el árbol y buscar el primer Node de cada nivel. Luego inicialice una variable para verificar si su vista izquierda está ordenada o no. Si no está ordenado, entonces podemos romper el bucle e imprimir falso; de lo contrario, el bucle continúa y, por último, imprime verdadero.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Check if the Left
// View of the given tree is Sorted or not
#include <bits/stdc++.h>
using namespace std;
// Binary Tree Node
struct node {
int val;
struct node *right, *left;
};
// Utility function to create a new node
struct node* newnode(int key)
{
struct node* temp = new node;
temp->val = key;
temp->right = NULL;
temp->left = NULL;
return temp;
}
// Function to find left view
// and check if it is sorted
void func(node* root)
{
// queue to hold values
queue<node*> q;
// variable to check whether
// level order is sorted or not
bool t = true;
q.push(root);
int i = -1, j = -1, k = -1;
// Iterate until the queue is empty
while (!q.empty()) {
int h = q.size();
// Traverse every level in tree
while (h > 0) {
root = q.front();
// variable for initial level
if (i == -1) {
j = root->val;
}
// checking values are sorted or not
if (i == -2) {
if (j <= root->val) {
j = root->val;
i = -3;
}
else {
t = false;
break;
}
}
// Push left value if it is not null
if (root->left != NULL) {
q.push(root->left);
}
// Push right value if it is not null
if (root->right != NULL) {
q.push(root->right);
}
h = h - 1;
// Pop out the values from queue
q.pop();
}
i = -2;
// Check if the value are not
// sorted then break the loop
if (t == false) {
break;
}
}
if (t)
cout << "true" << endl;
else
cout << "false" << endl;
}
// Driver code
int main()
{
struct node* root = newnode(10);
root->right = newnode(50);
root->right->right = newnode(15);
root->left = newnode(20);
root->left->left = newnode(50);
root->left->right = newnode(23);
root->right->left = newnode(10);
func(root);
return 0;
}
Java
// Java implementation to check if the left
// view of the given tree is sorted or not
import java.util.*;
class GFG{
// Binary Tree Node
static class node
{
int val;
node right, left;
};
// Utility function to create a new node
static node newnode(int key)
{
node temp = new node();
temp.val = key;
temp.right = null;
temp.left = null;
return temp;
}
// Function to find left view
// and check if it is sorted
static void func(node root)
{
// Queue to hold values
Queue<node> q = new LinkedList<>();
// Variable to check whether
// level order is sorted or not
boolean t = true;
q.add(root);
int i = -1, j = -1;
// Iterate until the queue is empty
while (!q.isEmpty())
{
int h = q.size();
// Traverse every level in tree
while (h > 0)
{
root = q.peek();
// Variable for initial level
if (i == -1)
{
j = root.val;
}
// Checking values are sorted or not
if (i == -2)
{
if (j <= root.val)
{
j = root.val;
i = -3;
}
else
{
t = false;
break;
}
}
// Push left value if it is not null
if (root.left != null)
{
q.add(root.left);
}
// Push right value if it is not null
if (root.right != null)
{
q.add(root.right);
}
h = h - 1;
// Pop out the values from queue
q.remove();
}
i = -2;
// Check if the value are not
// sorted then break the loop
if (t == false)
{
break;
}
}
if (t)
System.out.print("true" + "\n");
else
System.out.print("false" + "\n");
}
// Driver code
public static void main(String[] args)
{
node root = newnode(10);
root.right = newnode(50);
root.right.right = newnode(15);
root.left = newnode(20);
root.left.left = newnode(50);
root.left.right = newnode(23);
root.right.left = newnode(10);
func(root);
}
}
// This code is contributed by gauravrajput1
C#
// C# implementation to check if the left
// view of the given tree is sorted or not
using System;
using System.Collections.Generic;
class GFG{
// Binary Tree Node
class node
{
public int val;
public node right, left;
};
// Utility function to create a new node
static node newnode(int key)
{
node temp = new node();
temp.val = key;
temp.right = null;
temp.left = null;
return temp;
}
// Function to find left view
// and check if it is sorted
static void func(node root)
{
// Queue to hold values
Queue<node> q = new Queue<node>();
// Variable to check whether
// level order is sorted or not
bool t = true;
q.Enqueue(root);
int i = -1, j = -1;
// Iterate until the queue is empty
while (q.Count != 0)
{
int h = q.Count;
// Traverse every level in tree
while (h > 0)
{
root = q.Peek();
// Variable for initial level
if (i == -1)
{
j = root.val;
}
// Checking values are sorted or not
if (i == -2)
{
if (j <= root.val)
{
j = root.val;
i = -3;
}
else
{
t = false;
break;
}
}
// Push left value if it is not null
if (root.left != null)
{
q.Enqueue(root.left);
}
// Push right value if it is not null
if (root.right != null)
{
q.Enqueue(root.right);
}
h = h - 1;
// Pop out the values from queue
q.Dequeue();
}
i = -2;
// Check if the value are not
// sorted then break the loop
if (t == false)
{
break;
}
}
if (t)
Console.Write("true" + "\n");
else
Console.Write("false" + "\n");
}
// Driver code
public static void Main(String[] args)
{
node root = newnode(10);
root.right = newnode(50);
root.right.right = newnode(15);
root.left = newnode(20);
root.left.left = newnode(50);
root.left.right = newnode(23);
root.right.left = newnode(10);
func(root);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript implementation to check if the left
// view of the given tree is sorted or not
// Binary Tree Node
class node
{
constructor(key) {
this.left = null;
this.right = null;
this.val = key;
}
}
// Utility function to create a new node
function newnode(key)
{
let temp = new node(key);
return temp;
}
// Function to find left view
// and check if it is sorted
function func(root)
{
// Queue to hold values
let q = [];
// Variable to check whether
// level order is sorted or not
let t = true;
q.push(root);
let i = -1, j = -1;
// Iterate until the queue is empty
while (q.length > 0)
{
let h = q.length;
// Traverse every level in tree
while (h > 0)
{
root = q[0];
// Variable for initial level
if (i == -1)
{
j = root.val;
}
// Checking values are sorted or not
if (i == -2)
{
if (j <= root.val)
{
j = root.val;
i = -3;
}
else
{
t = false;
break;
}
}
// Push left value if it is not null
if (root.left != null)
{
q.push(root.left);
}
// Push right value if it is not null
if (root.right != null)
{
q.push(root.right);
}
h = h - 1;
// Pop out the values from queue
q.shift();
}
i = -2;
// Check if the value are not
// sorted then break the loop
if (t == false)
{
break;
}
}
if (t)
document.write("true" + "</br>");
else
document.write("false" + "</br>");
}
let root = newnode(10);
root.right = newnode(50);
root.right.right = newnode(15);
root.left = newnode(20);
root.left.left = newnode(50);
root.left.right = newnode(23);
root.right.left = newnode(10);
func(root);
// This code is contributed by decode2207.
</script>
Producción:
true
Complejidad del tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por vabzcode12 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA