Dado un árbol binario que consta solo de ‘(‘ y ‘)’ , se considera que un nivel está equilibrado si los Nodes del nivel que tienen paréntesis están equilibrados de izquierda a derecha. La tarea es contar el número total de niveles equilibrados en un árbol binario.
Ejemplos:
Entrada: (
/ \
( )
/ \ \
( ) (
/ \ \ \
( ( ) )Salida: 2
Explicación:
En los Niveles 2 y 4, los paréntesis están balanceados.Entrada: )
/ \
( )
/ \
( )
/
(Salida: 2
Explicación:
En el Nivel 2 y 3, los paréntesis están balanceados.
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una cola para realizar el cruce de orden de palanca en un árbol binario dado .
- Inicialice una pila para comprobar en cada nivel si los paréntesis están equilibrados o no .
- Atraviesa cada nivel uno por uno y realiza los siguientes pasos:
- Si el valor del Node actual es ‘(‘ , introdúzcalo en la pila .
- Si el valor del Node actual es ‘)’ , compruebe si la pila está vacía o no . Si no está vacío y la parte superior de la pila es ‘(‘ , sáquelo de la pila .
- De lo contrario, concluya que los paréntesis no están balanceados.
- Y al final del recorrido, si se encuentra que la pila está vacía, entonces concluya que los paréntesis están equilibrados. De lo contrario, concluya que los paréntesis no están balanceados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for Number of levels having balanced
// parentheses in a Binary Tree
#include <bits/stdc++.h>
using namespace std;
// Class containing left and
// right child of current
// node and key value
struct Node {
Node* left;
Node* right;
int key;
Node(int item)
{
key = item;
this->left = nullptr;
this->right = nullptr;
}
};
// Root of Binary Tree
Node* root = nullptr;
// Function to count levels in the
// Binary Tree having balanced parentheses
int countbal(Node* root)
{
// Stores nodes of each level
queue<Node*> que;
que.push(root);
// Stores required count of
// levels with balanced parentheses
int ans = 0;
// Iterate until false
while (true)
{
// Stores parentheses
stack<char> stk;
bool flag = true;
int len = que.size();
// If length is false
if (len == 0) {
break;
}
while (len > 0)
{
// Pop 0 from queue
// and store it in temp
Node* temp = que.front();
que.pop();
// Check if temp.key
// is equal to '('
if (temp->key == '(')
{
// push '(' into stack
stk.push('(');
}
else
{
// If stk is not empty and the
// last element in the stack is '(
if (stk.size() > 0 && stk.top() == '(')
{
// Pop from stack
stk.pop();
}
else
{
// Mark flag as False
flag = false;
}
}
// If tmp.left is True
if (temp->left != nullptr)
{
// push temp.left into queue
que.push(temp->left);
}
// If tmp.right is True
if (temp->right != nullptr)
{
// push temp.right into queue
que.push(temp->right);
}
// Decrement length by 1
len--;
}
// If flag is True
// and stk is False
if (flag && stk.size() > 0)
{
ans += 1;
}
}
return ans;
}
int main()
{
/*create root*/
// creating all its child
root = new Node('(');
root->left = new Node('(');
root->right = new Node(')');
root->left->left = new Node('(');
root->left->right = new Node(')');
root->right->right = new Node('(');
root->left->left->left = new Node('(');
root->left->left->right = new Node('(');
root->right->right->left = new Node(')');
root->right->right->right = new Node(')');
// function call and ans print
cout << countbal(root);
return 0;
}
// This code is contributed by suresh07.
Java
// Java program for Number of levels having balanced
// parentheses in a Binary Tree
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/* Class containing left and right child of current
node and key value*/
class Node {
char key;
Node left, right;
public Node(char item)
{
key = item;
left = right = null;
}
}
// A Java program to introduce Binary Tree
class BinaryTree
{
// Root of Binary Tree
Node root;
// Constructors
BinaryTree(char key) { root = new Node(key); }
BinaryTree() { root = null; }
// Function to count levels in the
// Binary Tree having balanced parentheses
public static int countbal(Node root)
{
// Stores nodes of each level
Queue<Node> que = new LinkedList<>();
que.add(root);
// Stores required count of
// levels with balanced parentheses
int ans = 0;
// Iterate until false
while (true)
{
// Stores parentheses
Stack<Character> stk = new Stack<>();
boolean flag = true;
int len = que.size();
// If length is false
if (len == 0) {
break;
}
while (len > 0)
{
// Pop 0 from queue
// and store it in temp
Node temp = que.remove();
// Check if temp.key
// is equal to '('
if (temp.key == '(')
{
// push '(' into stack
stk.push('(');
}
else
{
// If stk is not empty and the
// last element in the stack is '(
if (stk.size() > 0
&& stk.peek() == '(')
{
// Pop from stack
stk.pop();
}
else
{
// Mark flag as False
flag = false;
}
}
// If tmp.left is True
if (temp.left != null)
{
// push temp.left into queue
que.add(temp.left);
}
// If tmp.right is True
if (temp.right != null)
{
// push temp.right into queue
que.add(temp.right);
}
// Decrement length by 1
len--;
}
// If flag is True
// and stk is False
if (flag && stk.size() > 0)
{
ans += 1;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*create root*/
// creating all its child
tree.root = new Node('(');
tree.root.left = new Node('(');
tree.root.right = new Node(')');
tree.root.left.left = new Node('(');
tree.root.left.right = new Node(')');
tree.root.right.right = new Node('(');
tree.root.left.left.left = new Node('(');
tree.root.left.left.right = new Node('(');
tree.root.right.right.left = new Node(')');
tree.root.right.right.right = new Node(')');
// function call and ans print
System.out.println(countbal(tree.root));
}
}
// This code is contributed by adity7409.
Python3
# Python Code for above approach
# Structure of a Tree Node
class TreeNode:
def __init__(self, val='',
left=None, right=None):
self.val = val
self.left = left
self.right = right
# Function to count levels in the
# Binary Tree having balanced parentheses
def countBal(root):
# Stores nodes of each level
que = [root]
# Stores required count of
# levels with balanced parentheses
ans = 0
# Iterate until false
while True:
# Stores parentheses
stk = []
flag = True
length = len(que)
# If length is false
if not length:
break
while length:
# Pop 0 from queue
# and store it in temp
temp = que.pop(0)
# Check if temp.val
# is equal to '('
if temp.val == '(':
# Append '(' into stack
stk.append('(')
else:
# If stk is not empty and the
# last element in the stack is '('
if stk and stk[-1] == '(':
# Pop from stack
stk.pop()
else:
# Mark flag as False
flag = False
# If tmp.left is True
if temp.left:
# Append temp.left into queue
que.append(temp.left)
# If tmp.right is True
if temp.right:
# Append temp.right into queue
que.append(temp.right)
# Decrement length by 1
length -= 1
# If flag is True
# and stk is False
if flag and not stk:
ans += 1
# Return ans
return ans
# Driver Code
root = TreeNode('(')
root.left = TreeNode('(')
root.right = TreeNode(')')
root.left.left = TreeNode('(')
root.left.right = TreeNode(')')
root.right.right = TreeNode('(')
root.left.left.left = TreeNode('(')
root.left.left.right = TreeNode('(')
root.right.right.left = TreeNode(')')
root.right.right.right = TreeNode(')')
print(countBal(root))
C#
// C# program for Number of levels having balanced
// parentheses in a Binary Tree
using System;
using System.Collections;
class GFG {
// Class containing left and
// right child of current
// node and key value
class Node {
public int key;
public Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// Root of Binary Tree
static Node root = null;
// Function to count levels in the
// Binary Tree having balanced parentheses
static int countbal(Node root)
{
// Stores nodes of each level
Queue que = new Queue();
que.Enqueue(root);
// Stores required count of
// levels with balanced parentheses
int ans = 0;
// Iterate until false
while (true)
{
// Stores parentheses
Stack stk = new Stack();
bool flag = true;
int len = que.Count;
// If length is false
if (len == 0) {
break;
}
while (len > 0)
{
// Pop 0 from queue
// and store it in temp
Node temp = (Node)que.Peek();
que.Dequeue();
// Check if temp.key
// is equal to '('
if (temp.key == '(')
{
// push '(' into stack
stk.Push('(');
}
else
{
// If stk is not empty and the
// last element in the stack is '(
if (stk.Count > 0
&& (char)stk.Peek() == '(')
{
// Pop from stack
stk.Pop();
}
else
{
// Mark flag as False
flag = false;
}
}
// If tmp.left is True
if (temp.left != null)
{
// push temp.left into queue
que.Enqueue(temp.left);
}
// If tmp.right is True
if (temp.right != null)
{
// push temp.right into queue
que.Enqueue(temp.right);
}
// Decrement length by 1
len--;
}
// If flag is True
// and stk is False
if (flag && stk.Count > 0)
{
ans += 1;
}
}
return ans;
}
static void Main()
{
/*create root*/
// creating all its child
root = new Node('(');
root.left = new Node('(');
root.right = new Node(')');
root.left.left = new Node('(');
root.left.right = new Node(')');
root.right.right = new Node('(');
root.left.left.left = new Node('(');
root.left.left.right = new Node('(');
root.right.right.left = new Node(')');
root.right.right.right = new Node(')');
// function call and ans print
Console.Write(countbal(root));
}
}
// This code is contributed by decode2207.
Javascript
<script>
// JavaScript program for Number of levels having balanced
// parentheses in a Binary Tree
class Node
{
constructor(item) {
this.left = null;
this.right = null;
this.key = item;
}
}
// Root of Binary Tree
let root;
root = null;
// Function to count levels in the
// Binary Tree having balanced parentheses
function countbal(root)
{
// Stores nodes of each level
let que = [];
que.push(root);
// Stores required count of
// levels with balanced parentheses
let ans = 0;
// Iterate until false
while (true)
{
// Stores parentheses
let stk = [];
let flag = true;
let len = que.length;
// If length is false
if (len == 0) {
break;
}
while (len > 0)
{
// Pop 0 from queue
// and store it in temp
let temp = que.shift();
// Check if temp.key
// is equal to '('
if (temp.key == '(')
{
// push '(' into stack
stk.push('(');
}
else
{
// If stk is not empty and the
// last element in the stack is '(
if (stk.length > 0
&& stk[stk.length - 1] == '(')
{
// Pop from stack
stk.pop();
}
else
{
// Mark flag as False
flag = false;
}
}
// If tmp.left is True
if (temp.left != null)
{
// push temp.left into queue
que.push(temp.left);
}
// If tmp.right is True
if (temp.right != null)
{
// push temp.right into queue
que.push(temp.right);
}
// Decrement length by 1
len--;
}
// If flag is True
// and stk is False
if (flag && stk.length > 0)
{
ans += 1;
}
}
return ans;
}
/*create root*/
// creating all its child
root = new Node('(');
root.left = new Node('(');
root.right = new Node(')');
root.left.left = new Node('(');
root.left.right = new Node(')');
root.right.right = new Node('(');
root.left.left.left = new Node('(');
root.left.left.right = new Node('(');
root.right.right.left = new Node(')');
root.right.right.right = new Node(')');
// function call and ans print
document.write(countbal(root));
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA