Dado un Árbol Binario y un entero positivo K . La tarea es verificar si el BST balanceado de tamaño K existe en un árbol binario dado o no. Si existe, imprima » Sí»; de lo contrario, imprima » No» .
Ejemplos:
Input: K = 4,
Below is the given Tree:
15
/ \
10 26
/ \ / \
5 12 25 40
/ / \
20 35 50
\
60
Output: Yes
Explanation:
Subtree of the given tree with
size k is given below:
40
/ \
35 50
\
60
Input: K = 4,
Below is the given Tree:
18
/
9
/ \
7 10
Output: No
Explanation:
There is no subtree of size K
which forms a balanced BT.
Enfoque: La idea es utilizar Post Order Traversal . Los siguientes son los pasos para resolver el problema:
- Realice un Post Order Traversal en el árbol dado y verifique la condición BST para cada Node donde el valor más grande en el subárbol izquierdo debe ser menor que el valor actual y el valor más pequeño en el subárbol derecho debe ser mayor que el valor actual.
- Luego verifique si el BST está equilibrado o no, es decir, la diferencia absoluta entre el subárbol izquierdo y derecho debe ser 0 o 1 .
- Luego, pase los valores que regresan de los subárboles al padre.
- Realice los pasos anteriores para todos los Nodes y tome la variable booleana ans , que inicialmente se marca como falsa y se usa para verificar si hay un BST equilibrado o no.
- Si se encuentra un BST equilibrado de tamaño K , imprima «Sí» , de lo contrario, imprima «No» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// A tree node
struct node {
int data;
node* left;
node* right;
};
// Structure of temporary variable
struct minMax {
bool isBST;
bool balanced;
int size;
int height;
int min;
int max;
};
// Function to create the node
node* createNode(int value)
{
node* temp = new node();
temp->left = NULL;
temp->right = NULL;
temp->data = value;
}
// Utility function to find Balanced
// BST of size k
minMax findBalancedBstUtil(node* root,
int k, bool& ans)
{
// Base condition
if (root == NULL)
return { true, true, 0, 0,
INT_MAX, INT_MIN };
// Temporary variable
minMax temp;
// Recursive call for left sub-tree
minMax lsTree
= findBalancedBstUtil(root->left,
k, ans);
if (ans == true)
return temp;
// Recursive call for right sub-tree
minMax rsTree
= findBalancedBstUtil(root->right,
k, ans);
if (ans == true)
return temp;
// Check those conditions which
// violated the rules of BST
if (!lsTree.isBST || !rsTree.isBST
|| lsTree.max > root->data
|| rsTree.min < root->data) {
temp.isBST = false;
return temp;
}
// Check whether the Bst is
// height balanced or not
if (abs(lsTree.height
- rsTree.height)
== 1
|| abs(lsTree.height
- rsTree.height)
== 0)
temp.balanced = true;
else
temp.balanced = false;
// Make the variable true
// as sub-tree is BST
temp.isBST = true;
// Store the size
temp.size = 1 + lsTree.size
+ rsTree.size;
// Store the height
temp.height = max(lsTree.height,
rsTree.height)
+ 1;
// Store the minimum of BST
temp.min = root->left != NULL
? lsTree.min
: root->data;
// Store the maximum of BST
temp.max = root->right != NULL
? rsTree.max
: root->data;
// Condition to check whether the
// size of Balanced BST is K or not
if (temp.balanced == true
&& temp.size == k) {
ans = true;
}
// Return the temporary variable
// with updated data
return temp;
}
// Function to find the Balanced
// BST of size k
string findBalancedBst(node* root,
int k)
{
bool ans = false;
// Utility function call
findBalancedBstUtil(root, k, ans);
return ans == true ? "Yes" : "No";
}
// Driver Code
int main()
{
// Given Binary Tree
node* root = createNode(15);
root->left = createNode(10);
root->right = createNode(26);
root->left->left = createNode(5);
root->left->right = createNode(12);
root->right->left = createNode(25);
root->right->left->left = createNode(20);
root->right->right = createNode(40);
root->right->right->left = createNode(35);
root->right->right->right = createNode(50);
root->right->right->right->right = createNode(60);
int k = 4;
// Function Call
cout << findBalancedBst(root, k);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static boolean ans;
// A tree node
static class node
{
int data;
node left;
node right;
};
// Structure of temporary variable
static class minMax
{
boolean isBST;
boolean balanced;
int size;
int height;
int min;
int max;
public minMax(boolean isBST, boolean balanced,
int size, int height, int min,
int max)
{
super();
this.isBST = isBST;
this.balanced = balanced;
this.size = size;
this.height = height;
this.min = min;
this.max = max;
}
public minMax()
{
// TODO Auto-generated constructor stub
}
};
// Function to create the node
static node createNode(int value)
{
node temp = new node();
temp.left = null;
temp.right = null;
temp.data = value;
return temp;
}
// Utility function to find Balanced
// BST of size k
static minMax findBalancedBstUtil(node root,
int k)
{
// Base condition
if (root == null)
return new minMax(true, true, 0, 0,
Integer.MAX_VALUE,
Integer.MIN_VALUE );
// Temporary variable
minMax temp = new minMax();
// Recursive call for left sub-tree
minMax lsTree = findBalancedBstUtil(root.left,
k);
if (ans == true)
return temp;
// Recursive call for right sub-tree
minMax rsTree = findBalancedBstUtil(root.right,
k);
if (ans == true)
return temp;
// Check those conditions which
// violated the rules of BST
if (!lsTree.isBST || !rsTree.isBST ||
lsTree.max > root.data ||
rsTree.min < root.data)
{
temp.isBST = false;
return temp;
}
// Check whether the Bst is
// height balanced or not
if (Math.abs(lsTree.height -
rsTree.height) == 1 ||
Math.abs(lsTree.height -
rsTree.height) == 0)
temp.balanced = true;
else
temp.balanced = false;
// Make the variable true
// as sub-tree is BST
temp.isBST = true;
// Store the size
temp.size = 1 + lsTree.size +
rsTree.size;
// Store the height
temp.height = Math.max(lsTree.height,
rsTree.height) + 1;
// Store the minimum of BST
temp.min = root.left != null ?
lsTree.min : root.data;
// Store the maximum of BST
temp.max = root.right != null ?
rsTree.max : root.data;
// Condition to check whether the
// size of Balanced BST is K or not
if (temp.balanced == true &&
temp.size == k)
{
ans = true;
}
// Return the temporary variable
// with updated data
return temp;
}
// Function to find the Balanced
// BST of size k
static String findBalancedBst(node root,
int k)
{
ans = false;
// Utility function call
findBalancedBstUtil(root, k);
return ans == true ? "Yes" : "No";
}
// Driver Code
public static void main(String[] args)
{
// Given Binary Tree
node root = createNode(15);
root.left = createNode(10);
root.right = createNode(26);
root.left.left = createNode(5);
root.left.right = createNode(12);
root.right.left = createNode(25);
root.right.left.left = createNode(20);
root.right.right = createNode(40);
root.right.right.left = createNode(35);
root.right.right.right = createNode(50);
root.right.right.right.right = createNode(60);
int k = 4;
// Function call
System.out.print(findBalancedBst(root, k));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach import sys ans = False # A tree node class createNode: def __init__(self, data): self.data = data self.left = None self.right = None # Structure of temporary variable class newMinMax: def __init__(self, isBST, balanced, size, height, mn, mx): self.isBST = isBST self.balanced = balanced self.size = size self.height = height self.mn = mn self.mx = mx # Utility function to find Balanced # BST of size k def findBalancedBstUtil(root, k): global ans # Base condition if (root == None): return newMinMax(True, True, 0, 0, sys.maxsize, -sys.maxsize - 1) # Temporary variable temp = newMinMax(True, True, 0, 0, sys.maxsize, -sys.maxsize - 1) # Recursive call for left sub-tree lsTree = findBalancedBstUtil(root.left, k) if (ans == True): return temp # Recursive call for right sub-tree rsTree = findBalancedBstUtil(root.right, k) if (ans == True): return temp # Check those conditions which # violated the rules of BST if (lsTree.isBST == False or rsTree.isBST == False or lsTree.mx > root.data or rsTree.mn < root.data): temp.isBST = False return temp # Check whether the Bst is # height balanced or not if (abs(lsTree.height - rsTree.height) == 1 or abs(lsTree.height - rsTree.height) == 0): temp.balanced = True else: temp.balanced = False # Make the variable true # as sub-tree is BST temp.isBST = True # Store the size temp.size = 1 + lsTree.size + rsTree.size # Store the height temp.height = max(lsTree.height , rsTree.height) + 1 # Store the minimum of BST if root.left != None: temp.mn = lsTree.mn else: temp.mn = root.data # Store the maximum of BST if root.right != None: temp.mx = rsTree.mx else: temp.mx = root.data # Condition to check whether the # size of Balanced BST is K or not if (temp.balanced == True and temp.size == k): ans = True # Return the temporary variable # with updated data return temp # Function to find the Balanced # BST of size k def findBalancedBst(root, k): global ans # Utility function call findBalancedBstUtil(root, k) if ans == True: return "Yes" else: return "No" # Driver Code if __name__ == '__main__': # Given Binary Tree root = createNode(15) root.left = createNode(10) root.right = createNode(26) root.left.left = createNode(5) root.left.right = createNode(12) root.right.left = createNode(25) root.right.left.left = createNode(20) root.right.right = createNode(40) root.right.right.left = createNode(35) root.right.right.right = createNode(50) root.right.right.right.right = createNode(60) k = 4 # Function Call print(findBalancedBst(root, k)) # This code is contributed by ipg2016107
C#
// C# program for the
// above approach
using System;
class GFG{
static bool ans;
// A tree node
public class node
{
public int data;
public node left;
public node right;
};
// Structure of temporary
// variable
public class minMax
{
public bool isBST;
public bool balanced;
public int size;
public int height;
public int min;
public int max;
public minMax(bool isBST, bool balanced,
int size, int height, int min,
int max)
{
this.isBST = isBST;
this.balanced = balanced;
this.size = size;
this.height = height;
this.min = min;
this.max = max;
}
public minMax()
{
// TODO Auto-generated constructor stub
}
};
// Function to create the node
static node createNode(int value)
{
node temp = new node();
temp.left = null;
temp.right = null;
temp.data = value;
return temp;
}
// Utility function to find Balanced
// BST of size k
static minMax findBalancedBstUtil(node root,
int k)
{
// Base condition
if (root == null)
return new minMax(true, true, 0, 0,
int.MaxValue,
int.MinValue);
// Temporary variable
minMax temp = new minMax();
// Recursive call for left sub-tree
minMax lsTree =
findBalancedBstUtil(root.left, k);
if (ans == true)
return temp;
// Recursive call for right sub-tree
minMax rsTree =
findBalancedBstUtil(root.right, k);
if (ans == true)
return temp;
// Check those conditions which
// violated the rules of BST
if (!lsTree.isBST || !rsTree.isBST ||
lsTree.max > root.data ||
rsTree.min < root.data)
{
temp.isBST = false;
return temp;
}
// Check whether the Bst is
// height balanced or not
if (Math.Abs(lsTree.height -
rsTree.height) == 1 ||
Math.Abs(lsTree.height -
rsTree.height) == 0)
temp.balanced = true;
else
temp.balanced = false;
// Make the variable true
// as sub-tree is BST
temp.isBST = true;
// Store the size
temp.size = 1 + lsTree.size +
rsTree.size;
// Store the height
temp.height = Math.Max(lsTree.height,
rsTree.height) + 1;
// Store the minimum of BST
temp.min = root.left != null ?
lsTree.min : root.data;
// Store the maximum of BST
temp.max = root.right != null ?
rsTree.max : root.data;
// Condition to check whether the
// size of Balanced BST is K or not
if (temp.balanced == true &&
temp.size == k)
{
ans = true;
}
// Return the temporary
// variable with updated data
return temp;
}
// Function to find the Balanced
// BST of size k
static String findBalancedBst(node root,
int k)
{
ans = false;
// Utility function call
findBalancedBstUtil(root, k);
return ans == true ? "Yes" : "No";
}
// Driver Code
public static void Main(String[] args)
{
// Given Binary Tree
node root = createNode(15);
root.left = createNode(10);
root.right = createNode(26);
root.left.left = createNode(5);
root.left.right = createNode(12);
root.right.left = createNode(25);
root.right.left.left = createNode(20);
root.right.right = createNode(40);
root.right.right.left = createNode(35);
root.right.right.right = createNode(50);
root.right.right.right.right = createNode(60);
int k = 4;
// Function call
Console.Write(findBalancedBst(root, k));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
let ans = false;
// A tree Node
class node
{
constructor(value) {
this.left = null;
this.right = null;
this.data = value;
}
}
// Structure of temporary variable
class minMax
{
constructor(isBST, balanced, size, height, min, max)
{
this.isBST = isBST;
this.balanced = balanced;
this.size = size;
this.height = height;
this.min = min;
this.max = max;
}
}
// Function to create the node
function createNode(value)
{
let temp = new node(value);
return temp;
}
// Utility function to find Balanced
// BST of size k
function findBalancedBstUtil(root, k)
{
// Base condition
if (root == null)
return new minMax(true, true, 0, 0,
Number.MAX_VALUE,
Number.MIN_VALUE );
// Temporary variable
let temp = new minMax();
// Recursive call for left sub-tree
let lsTree = findBalancedBstUtil(root.left,
k);
if (ans == true)
return temp;
// Recursive call for right sub-tree
let rsTree = findBalancedBstUtil(root.right,
k);
if (ans == true)
return temp;
// Check those conditions which
// violated the rules of BST
if (!lsTree.isBST || !rsTree.isBST ||
lsTree.max > root.data ||
rsTree.min < root.data)
{
temp.isBST = false;
return temp;
}
// Check whether the Bst is
// height balanced or not
if (Math.abs(lsTree.height -
rsTree.height) == 1 ||
Math.abs(lsTree.height -
rsTree.height) == 0)
temp.balanced = true;
else
temp.balanced = false;
// Make the variable true
// as sub-tree is BST
temp.isBST = true;
// Store the size
temp.size = 1 + lsTree.size +
rsTree.size;
// Store the height
temp.height = Math.max(lsTree.height,
rsTree.height) + 1;
// Store the minimum of BST
temp.min = root.left != null ?
lsTree.min : root.data;
// Store the maximum of BST
temp.max = root.right != null ?
rsTree.max : root.data;
// Condition to check whether the
// size of Balanced BST is K or not
if (temp.balanced == true &&
temp.size == k)
{
ans = true;
}
// Return the temporary variable
// with updated data
return temp;
}
// Function to find the Balanced
// BST of size k
function findBalancedBst(root, k)
{
ans = false;
// Utility function call
findBalancedBstUtil(root, k);
return ans == true ? "Yes" : "No";
}
// Given Binary Tree
let root = createNode(15);
root.left = createNode(10);
root.right = createNode(26);
root.left.left = createNode(5);
root.left.right = createNode(12);
root.right.left = createNode(25);
root.right.left.left = createNode(20);
root.right.right = createNode(40);
root.right.right.left = createNode(35);
root.right.right.right = createNode(50);
root.right.right.right.right = createNode(60);
let k = 4;
// Function call
document.write(findBalancedBst(root, k));
// This code is contributed by mukesh07.
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA