Dado un árbol binario, compruebe si es un árbol binario sesgado o no. Un árbol sesgado es un árbol en el que cada Node tiene solo un Node secundario o ninguno.
Ejemplos:
Input : 5
/
4
\
3
/
2
Output : Yes
Input : 5
/
4
\
3
/ \
2 4
Output : No
La idea es comprobar si un Node tiene dos hijos. Si el Node tiene dos hijos, devuelve falso; de lo contrario, calcule recursivamente si el subárbol con un hijo es un árbol sesgado. Si el Node es un Node hoja, devuelve verdadero.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Check whether a given
// binary tree is skewed binary tree or not?
#include <bits/stdc++.h>
using namespace std;
// A Tree node
struct Node {
int key;
struct Node *left, *right;
};
// Utility function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
bool isSkewedBT(Node* root)
{
// check if node is NULL or is a leaf node
if (root == NULL || (root->left == NULL &&
root->right == NULL))
return true;
// check if node has two children if
// yes, return false
if (root->left && root->right)
return false;
if (root->left)
return isSkewedBT(root->left);
return isSkewedBT(root->right);
}
// Driver program
int main()
{
/* 10
/ \
12 13
/ \
14 15
/ \ / \
21 22 23 24
Let us create Binary Tree shown in above example */
Node* root = newNode(10);
root->left = newNode(12);
root->left->right = newNode(15);
cout << isSkewedBT(root) << endl;
root = newNode(5);
root->right = newNode(4);
root->right->left = newNode(3);
root->right->left->right = newNode(2);
cout << isSkewedBT(root) << endl;
root = newNode(5);
root->left = newNode(4);
root->left->right = newNode(3);
root->left->right->left = newNode(2);
root->left->right->right = newNode(4);
cout << isSkewedBT(root) << endl;
}
Java
// Java program to Check whether a given
// binary tree is skewed binary tree or not?
class Solution
{
// A Tree node
static class Node {
int key;
Node left, right;
}
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
static boolean isSkewedBT(Node root)
{
// check if node is null or is a leaf node
if (root == null || (root.left == null &&
root.right == null))
return true;
// check if node has two children if
// yes, return false
if (root.left!=null && root.right!=null)
return false;
if (root.left!=null)
return isSkewedBT(root.left);
return isSkewedBT(root.right);
}
// Driver program
public static void main(String args[])
{
/* 10
/ \
12 13
/ \
14 15
/ \ / \
21 22 23 24
Let us create Binary Tree shown in above example */
Node root = newNode(10);
root.left = newNode(12);
root.left.right = newNode(15);
System.out.println( isSkewedBT(root)?1:0 );
root = newNode(5);
root.right = newNode(4);
root.right.left = newNode(3);
root.right.left.right = newNode(2);
System.out.println( isSkewedBT(root)?1:0 );
root = newNode(5);
root.left = newNode(4);
root.left.right = newNode(3);
root.left.right.left = newNode(2);
root.left.right.right = newNode(4);
System.out.println( isSkewedBT(root)?1:0 );
}
}
//contributed by Arnab Kundu
Python3
# Python3 program to Check whether a given # binary tree is skewed binary tree or not? # Binary Tree Node """ utility that allocates a newNode with the given key """ class newNode: # Construct to create a newNode def __init__(self, key): self.data = key self.left = None self.right = None def isSkewedBT(root): # check if node is None or is a leaf node if (root == None or (root.left == None and root.right == None)): return 1 # check if node has two children if # yes, return false if (root.left and root.right): return 0 if (root.left) : return isSkewedBT(root.left) return isSkewedBT(root.right) # Driver Code if __name__ == '__main__': """ 10 / \ 12 13 / \ 14 15 / \ / \ 21 22 23 24 Let us create Binary Tree shown in above example """ root = newNode(10) root.left = newNode(12) root.left.right = newNode(15) print(isSkewedBT(root)) root = newNode(5) root.right = newNode(4) root.right.left = newNode(3) root.right.left.right = newNode(2) print(isSkewedBT(root)) root = newNode(5) root.left = newNode(4) root.left.right = newNode(3) root.left.right.left = newNode(2) root.left.right.right = newNode(4) print(isSkewedBT(root)) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to Check whether a given
// binary tree is skewed binary tree or not?
using System;
public class GFG
{
// A Tree node
class Node
{
public int key;
public Node left, right;
}
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
static bool isSkewedBT(Node root)
{
// check if node is null or is a leaf node
if (root == null || (root.left == null &&
root.right == null))
return true;
// check if node has two children if
// yes, return false
if (root.left!=null && root.right!=null)
return false;
if (root.left!=null)
return isSkewedBT(root.left);
return isSkewedBT(root.right);
}
// Driver code
public static void Main()
{
/* 10
/ \
12 13
/ \
14 15
/ \ / \
21 22 23 24
Let us create Binary Tree shown in above example */
Node root = newNode(10);
root.left = newNode(12);
root.left.right = newNode(15);
Console.WriteLine( isSkewedBT(root)?1:0 );
root = newNode(5);
root.right = newNode(4);
root.right.left = newNode(3);
root.right.left.right = newNode(2);
Console.WriteLine( isSkewedBT(root)?1:0 );
root = newNode(5);
root.left = newNode(4);
root.left.right = newNode(3);
root.left.right.left = newNode(2);
root.left.right.right = newNode(4);
Console.WriteLine( isSkewedBT(root)?1:0 );
}
}
/* This code is contributed by Rajput-Ji*/
Javascript
<script>
// Javascript program to Check whether a given
// binary tree is skewed binary tree or not?
// Binary tree node
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.data = key;
}
}
// Utility function to create a new node
function newNode(key)
{
let temp = new Node(key);
return (temp);
}
function isSkewedBT(root)
{
// check if node is null or is a leaf node
if (root == null || (root.left == null &&
root.right == null))
return true;
// check if node has two children if
// yes, return false
if (root.left!=null && root.right!=null)
return false;
if (root.left!=null)
return isSkewedBT(root.left);
return isSkewedBT(root.right);
}
/* 10
/ \
12 13
/ \
14 15
/ \ / \
21 22 23 24
Let us create Binary Tree shown in above example */
let root = newNode(10);
root.left = newNode(12);
root.left.right = newNode(15);
document.write(isSkewedBT(root)?1 + "</br>":0 + "</br>");
root = newNode(5);
root.right = newNode(4);
root.right.left = newNode(3);
root.right.left.right = newNode(2);
document.write(isSkewedBT(root)?1 + "</br>":0 + "</br>");
root = newNode(5);
root.left = newNode(4);
root.left.right = newNode(3);
root.left.right.left = newNode(2);
root.left.right.right = newNode(4);
document.write(isSkewedBT(root)?1 + "</br>":0 + "</br>");
// This code is contributed by decode2207.
</script>
Producción
1 1 0
La complejidad temporal de esta solución es
Mejor caso: O(1) cuando root tiene dos hijos.
Peor caso: O(h) cuando el árbol es un árbol sesgado.
Espacio Auxiliar: O(h)
Aquí h es la altura del árbol.
Otro enfoque: (método iterativo)
También podemos verificar si un árbol está sesgado o no mediante el método iterativo utilizando el enfoque anterior.
implementación:
C++
// C++ program to Check whether a given
// binary tree is skewed binary tree or not using iterative
// method
#include <bits/stdc++.h>
using namespace std;
// A Tree node
struct Node {
int key;
struct Node *left, *right;
};
// Utility function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
bool isSkewedBT(Node* root)
{
while (root != NULL) {
// check if the node is a leaf node
if (root->left == NULL && root->right == NULL)
return true;
// check if node has two children if
// yes, return false
if (root->left != NULL && root->right != NULL)
return false;
// move towards left if it has a left child
if (root->left != NULL)
root = root->left;
// or move towards right if it has a right child
else
root = root->right;
}
return true;
}
// Driver program
int main()
{
/* 10
/ \
12 13
/ \
14 15
/ \ / \
21 22 23 24
Let us create Binary Tree shown in above example */
Node* root = newNode(10);
root->left = newNode(12);
root->left->right = newNode(15);
cout << isSkewedBT(root) << endl;
root = newNode(5);
root->right = newNode(4);
root->right->left = newNode(3);
root->right->left->right = newNode(2);
cout << isSkewedBT(root) << endl;
root = newNode(5);
root->left = newNode(4);
root->left->right = newNode(3);
root->left->right->left = newNode(2);
root->left->right->right = newNode(4);
cout << isSkewedBT(root) << endl;
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Java
// Java program to Check whether a given
// binary tree is skewed binary tree or not using iterative method
class Solution {
// A Tree node
static class Node {
int key;
Node left, right;
}
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
static boolean isSkewedBT(Node root)
{
while (root != null) {
// check if the node is a leaf node
if (root.left == null && root.right == null)
return true;
// check if node has two children if
// yes, return false
if (root.left!=null && root.right!=null)
return false;
// move towards left if it has a left child
if (root.left != null)
root = root.left;
// or move towards right if it has a right child
else
root = root.right;
}
return true;
}
// Driver program
public static void main(String args[])
{
/* 10
/ \
12 13
/ \
14 15
/ \ / \
21 22 23 24
Let us create Binary Tree shown in above example */
Node root = newNode(10);
root.left = newNode(12);
root.left.right = newNode(15);
System.out.println(isSkewedBT(root) ? 1 : 0);
root = newNode(5);
root.right = newNode(4);
root.right.left = newNode(3);
root.right.left.right = newNode(2);
System.out.println(isSkewedBT(root) ? 1 : 0);
root = newNode(5);
root.left = newNode(4);
root.left.right = newNode(3);
root.left.right.left = newNode(2);
root.left.right.right = newNode(4);
System.out.println(isSkewedBT(root) ? 1 : 0);
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Python3
# Python3 program to Check whether a given # binary tree is skewed binary tree or not using iterative method # Binary Tree Node """ utility that allocates a newNode with the given key """ class newNode: # Construct to create a newNode def __init__(self, key): self.data = key self.left = None self.right = None def isSkewedBT(root): while (root != None): # check if the node is a leaf node if (root.left == None and root.right == None): return 1 # check if node has two children if # yes, return false if (root.left != None and root.right != None): return 0 # move towards left if it has a left child if (root.left != None): root = root.left # or move towards right if it has a right child else: root = root.right return 1 # Driver Code if __name__ == '__main__': """ 10 / \ 12 13 / \ 14 15 / \ / \ 21 22 23 24 Let us create Binary Tree shown in above example """ root = newNode(10) root.left = newNode(12) root.left.right = newNode(15) print(isSkewedBT(root)) root = newNode(5) root.right = newNode(4) root.right.left = newNode(3) root.right.left.right = newNode(2) print(isSkewedBT(root)) root = newNode(5) root.left = newNode(4) root.left.right = newNode(3) root.left.right.left = newNode(2) root.left.right.right = newNode(4) print(isSkewedBT(root)) # This code is contributed by # Abhijeet Kumar(abhijeet19403)
C#
// C# program to Check whether a given
// binary tree is skewed binary tree or not using iterative method
using System;
public class GFG {
// A Tree node
class Node {
public int key;
public Node left, right;
}
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
static bool isSkewedBT(Node root)
{
while (root != null) {
// check if the node is a leaf node
if (root.left == null && root.right == null)
return true;
// check if node has two children if
// yes, return false
if (root.left != null && root.right != null)
return false;
// move towards left if it has a left child
if (root.left != null)
root = root.left;
// or move towards right if it has a right child
else
root = root.right;
}
return true;
}
// Driver code
public static void Main()
{
/* 10
/ \
12 13
/ \
14 15
/ \ / \
21 22 23 24
Let us create Binary Tree shown in above example */
Node root = newNode(10);
root.left = newNode(12);
root.left.right = newNode(15);
Console.WriteLine(isSkewedBT(root) ? 1 : 0);
root = newNode(5);
root.right = newNode(4);
root.right.left = newNode(3);
root.right.left.right = newNode(2);
Console.WriteLine(isSkewedBT(root) ? 1 : 0);
root = newNode(5);
root.left = newNode(4);
root.left.right = newNode(3);
root.left.right.left = newNode(2);
root.left.right.right = newNode(4);
Console.WriteLine(isSkewedBT(root) ? 1 : 0);
}
}
/* This code is contributed by Abhijeet
* Kumar(abhijeet19403)*/
Javascript
<script>
// Javascript program to Check whether a given
// binary tree is skewed binary tree or not?
// Binary tree node
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.data = key;
}
}
// Utility function to create a new node
function newNode(key)
{
let temp = new Node(key);
return (temp);
}
function isSkewedBT(root)
{
while (root != null) {
// check if the node is a leaf node
if (root.left == null && root.right == null)
return true;
// check if node has two children if
// yes, return false
if (root.left != null && root.right != null)
return false;
// move towards left if it has a left child
if (root.left != null)
root = root.left;
// or move towards right if it has a right child
else
root = root.right;
}
return true;
}
/* 10
/ \
12 13
/ \
14 15
/ \ / \
21 22 23 24
Let us create Binary Tree shown in above example */
let root = newNode(10);
root.left = newNode(12);
root.left.right = newNode(15);
document.write(isSkewedBT(root)?1 + "</br>":0 + "</br>");
root = newNode(5);
root.right = newNode(4);
root.right.left = newNode(3);
root.right.left.right = newNode(2);
document.write(isSkewedBT(root)?1 + "</br>":0 + "</br>");
root = newNode(5);
root.left = newNode(4);
root.left.right = newNode(3);
root.left.right.left = newNode(2);
root.left.right.right = newNode(4);
document.write(isSkewedBT(root)?1 + "</br>":0 + "</br>");
// This code is contributed by Abhijeet Kumar(abhijeet19403)
</script>
Producción
1 1 0
Complejidad de tiempo: O(n)
Como en el peor de los casos, tenemos que visitar todos los Nodes.
Espacio Auxiliar: O(1)
Como espacio adicional constante se utiliza.
Este enfoque fue aportado por Ahijeet Kumar .
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por gaddevarunteja y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA