Dada una string s que consta de paréntesis { ‘(‘ y ‘)’ } y números enteros, la tarea es construir un árbol binario a partir de ella e imprimir su recorrido Preorder .
Ejemplos:
Entrada: S = “1(2)(3)”
Salida: 1 2 3
Explicación: El árbol binario correspondiente es el siguiente:
1
/ \
2 3Entrada: “4(2(3)(1))(6(5))”
Salida: 4 2 3 1 6 5
Explicación:
El árbol binario correspondiente es el siguiente:4
/ \
2 6
/ \ /
3 1 5
Enfoque recursivo : consulte el artículo anterior para resolver el problema de forma recursiva.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque: este problema se puede resolver utilizando la estructura de datos de pila . Siga los pasos a continuación para resolver el problema:
- Actualice el carácter en la posición 0 como raíz del árbol binario e inicialice una pila stk .
- Iterar en el rango [1, N-1] usando la variable i :
- Al final de los pasos anteriores, devuelva el Node raíz del árbol binario.
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;
// Build a tree node having left and
// right pointers set to null initially
struct Node {
Node* left;
Node* right;
int data;
// Constructor to set the data of
// the newly created tree node
Node(int element)
{
data = element;
this->left = nullptr;
this->right = nullptr;
}
};
// Utility function to print
// preorder traversal of the tree
void preorder(Node* root)
{
if (!root)
return;
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
// Function to construct a
// tree using bracket notation
Node* constructTree(string s)
{
// First character is the root of the tree
Node* root = new Node(s[0] - '0');
// Stack used to store the
// previous root elements
stack<Node*> stk;
// Iterate over remaining characters
for (int i = 1; i < s.length(); i++) {
// If current character is '('
if (s[i] == '(') {
// Push root into stack
stk.push(root);
}
// If current character is ')'
else if (s[i] == ')') {
// Make root the top most
// element in the stack
root = stk.top();
// Remove the top node
stk.pop();
}
// If current character is a number
else {
// If left is null, then put the new
// node to the left and move to the
// left of the root
if (root->left == nullptr) {
Node* left = new Node(s[i] - '0');
root->left = left;
root = root->left;
}
// Otherwise, if right is null, then
// put the new node to the right and
// move to the right of the root
else if (root->right == nullptr) {
Node* right = new Node(s[i] - '0');
root->right = right;
root = root->right;
}
}
}
// Return the root
return root;
}
// Driver code
int main()
{
// Input
string s = "4(2(3)(1))(6(5))";
// Function calls
Node* root = constructTree(s);
preorder(root);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
// Class containing left and
// right child of current
// node and key value
static class Node {
public int data;
public Node left, right;
public Node(int element)
{
data = element;
left = right = null;
}
}
// Utility function to print
// preorder traversal of the tree
static void preorder(Node root)
{
if (root == null)
return;
System.out.print(root.data + " ");
preorder(root.left);
preorder(root.right);
}
// Function to construct a
// tree using bracket notation
static Node constructTree(String s)
{
// First character is the root of the tree
Node root = new Node(s.charAt(0) - '0');
// Stack used to store the
// previous root elements
Stack<Node> stk = new Stack<Node>();
// Iterate over remaining characters
for (int i = 1; i < s.length(); i++) {
// If current character is '('
if (s.charAt(i) == '(') {
// Push root into stack
stk.push(root);
}
// If current character is ')'
else if (s.charAt(i) == ')') {
// Make root the top most
// element in the stack
root = stk.peek();
// Remove the top node
stk.pop();
}
// If current character is a number
else {
// If left is null, then put the new
// node to the left and move to the
// left of the root
if (root.left == null) {
Node left = new Node(s.charAt(i) - '0');
root.left = left;
root = root.left;
}
// Otherwise, if right is null, then
// put the new node to the right and
// move to the right of the root
else if (root.right == null) {
Node right = new Node(s.charAt(i) - '0');
root.right = right;
root = root.right;
}
}
}
// Return the root
return root;
}
public static void main(String[] args) {
// Input
String s = "4(2(3)(1))(6(5))";
// Function calls
Node root = constructTree(s);
preorder(root);
}
}
// This code is contributed by divyesh072019.
Python3
# Python program for the above approach
# Build a tree node having left and
# right pointers set to null initially
class Node:
# Constructor to set the data of
# the newly created tree node
def __init__(self, element):
self.data = element
self.left = None
self.right = None
# Utility function to print
# preorder traversal of the tree
def preorder(root):
if (not root):
return
print(root.data, end = " ")
preorder(root.left)
preorder(root.right)
# Function to construct a
# tree using bracket notation
def constructTree(s):
# First character is the root of the tree
root = Node(ord(s[0]) - ord('0'))
# Stack used to store the
# previous root elements
stk = []
# Iterate over remaining characters
for i in range(1,len(s)):
# If current character is '('
if (s[i] == '('):
# Push root into stack
stk.append(root)
# If current character is ')'
elif (s[i] == ')'):
# Make root the top most
# element in the stack
root = stk[-1]
# Remove the top node
del stk[-1]
# If current character is a number
else:
# If left is null, then put the new
# node to the left and move to the
# left of the root
if (root.left == None):
left = Node(ord(s[i]) - ord('0'))
root.left = left
root = root.left
# Otherwise, if right is null, then
# put the new node to the right and
# move to the right of the root
elif (root.right == None):
right = Node(ord(s[i]) - ord('0'))
root.right = right
root = root.right
# Return the root
return root
# Driver code
if __name__ == '__main__':
# Input
s = "4(2(3)(1))(6(5))"
# Function calls
root = constructTree(s)
preorder(root)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG
{
// Class containing left and
// right child of current
// node and key value
class Node {
public int data;
public Node left, right;
public Node(int element)
{
data = element;
left = right = null;
}
}
// Utility function to print
// preorder traversal of the tree
static void preorder(Node root)
{
if (root == null)
return;
Console.Write(root.data + " ");
preorder(root.left);
preorder(root.right);
}
// Function to construct a
// tree using bracket notation
static Node constructTree(string s)
{
// First character is the root of the tree
Node root = new Node(s[0] - '0');
// Stack used to store the
// previous root elements
Stack stk = new Stack();
// Iterate over remaining characters
for (int i = 1; i < s.Length; i++) {
// If current character is '('
if (s[i] == '(') {
// Push root into stack
stk.Push(root);
}
// If current character is ')'
else if (s[i] == ')') {
// Make root the top most
// element in the stack
root = (Node)(stk.Peek());
// Remove the top node
stk.Pop();
}
// If current character is a number
else {
// If left is null, then put the new
// node to the left and move to the
// left of the root
if (root.left == null) {
Node left = new Node(s[i] - '0');
root.left = left;
root = root.left;
}
// Otherwise, if right is null, then
// put the new node to the right and
// move to the right of the root
else if (root.right == null) {
Node right = new Node(s[i] - '0');
root.right = right;
root = root.right;
}
}
}
// Return the root
return root;
}
// Driver code
static void Main()
{
// Input
string s = "4(2(3)(1))(6(5))";
// Function calls
Node root = constructTree(s);
preorder(root);
}
}
// This code is contributed by decode2207.
Javascript
<script>
// Javascript program for the above approach
class Node
{
constructor(element) {
this.left = null;
this.right = null;
this.data = element;
}
}
// Utility function to print
// preorder traversal of the tree
function preorder(root)
{
if (root == null)
return;
document.write(root.data + " ");
preorder(root.left);
preorder(root.right);
}
// Function to construct a
// tree using bracket notation
function constructTree(s)
{
// First character is the root of the tree
let root = new Node(s[0].charCodeAt() - '0'.charCodeAt());
// Stack used to store the
// previous root elements
let stk = [];
// Iterate over remaining characters
for (let i = 1; i < s.length; i++) {
// If current character is '('
if (s[i] == '(') {
// Push root into stack
stk.push(root);
}
// If current character is ')'
else if (s[i] == ')') {
// Make root the top most
// element in the stack
root = stk[stk.length - 1];
// Remove the top node
stk.pop();
}
// If current character is a number
else {
// If left is null, then put the new
// node to the left and move to the
// left of the root
if (root.left == null) {
let left = new Node(s[i].charCodeAt() - '0'.charCodeAt());
root.left = left;
root = root.left;
}
// Otherwise, if right is null, then
// put the new node to the right and
// move to the right of the root
else if (root.right == null) {
let right = new Node(s[i].charCodeAt() - '0'.charCodeAt());
root.right = right;
root = root.right;
}
}
}
// Return the root
return root;
}
// Input
let s = "4(2(3)(1))(6(5))";
// Function calls
let root = constructTree(s);
preorder(root);
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
4 2 3 1 6 5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ManjuKrishna y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA