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>
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