Dado un árbol binario , la tarea es imprimir el recorrido de abajo a la izquierda a arriba a la derecha del árbol binario dado , es decir, el recorrido de orden de nivel que tiene el nivel como Node de abajo a la izquierda a arriba a la derecha.
Ejemplos:
Entrada: A continuación se muestra el árbol dado:
Salida: 2 7 2 5 6 5 11 4 9
Explicación:
Nivel 1: 2 7 2 (hacia arriba desde la parte inferior izquierda a la derecha hasta la raíz)
Nivel 2: 5 6 5 (a la derecha de cada Node en la capa 1/o desde la parte inferior izquierda hacia arriba a la derecha en esta capa)
Nivel 3: 11 4 9 (a la derecha desde cada Node en la capa 2/o abajo a la izquierda hacia arriba a la derecha en esta capa)Entrada: 1 2 3 4 5 6 7
Salida: 4 2 1 5 6 3 2
Explicación
Capa 1: 4 2 1 (hacia arriba de izquierda a derecha hasta la raíz)
Capa 2: 5 6 3 (a la derecha de cada Node en la capa 1 /o de abajo a la izquierda a arriba a la derecha en esta capa)
Capa 3: 2 (a la derecha de cada Node en la capa 2/o de abajo a la izquierda a arriba a la derecha en esta capa)
Enfoque: La idea es utilizar la técnica de Búsqueda Primero en Amplitud . Siga los pasos necesarios para resolver este problema:
- Inicialice una capa en un árbol binario. Es una lista de Nodes que comienza desde el Node más a la izquierda de la parte inferior al lado de la capa anterior y termina con el Node más a la derecha de la parte superior al lado de la capa anterior.
- Cree una pila para almacenar todos los Nodes en cada capa.
- Inicialice una cola para mantener las » raíces » en cada capa, una raíz en una capa es un Node desde el cual se puede ir hacia abajo usando solo los hijos izquierdos.
- Empuje el Node raíz de la primera capa (la raíz del árbol) en la cola.
- Defina un indicador (digamos lyr_root ) un Node esperado al final de una capa que es el encabezado de capa actual, un encabezado de capa es el primer Node en una capa.
- Atraviese hasta que la cola no esté vacía y haga lo siguiente:
- Obtenga una raíz de capa desde el frente de la cola
- Si esta raíz de capa es el encabezado de capa de una nueva capa, extraiga todos los elementos de la pila , es decir, del elemento de capa anterior, e imprímalo.
- Atraviese la capa desde la parte superior derecha hasta la parte inferior izquierda y para cada elemento, si tiene un hijo derecho, compruebe si el Node atravesado es el encabezado de la capa o no. Si se determina que es cierto, cambie el indicador esperado para indicar el siguiente encabezado de capa.
- Empuje al niño correcto a la raíz en la cola.
- Empuje el Node atravesado en la pila.
- Después de atravesar todas las capas, es posible que la capa final aún esté en la pila, por lo que debemos extraer todos los elementos e imprimirlos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Node Structures
typedef struct Node {
int data;
Node* left;
Node* right;
} Node;
// Function to add the new Node in
// the Binary Tree
Node* newNode(int data)
{
Node* n;
// Create a new Node
n = new Node();
n->data = data;
n->right = NULL;
n->left = NULL;
return n;
}
// Function to traverse the tree in the
// order of bottom left to the upward
// right order
vector<int>
leftBottomTopRightTraversal(Node* root)
{
// Stores the data of the node
vector<int> rr;
// Stores every element in each layer
stack<int> r;
// Stores the roots in the layers
queue<Node*> roots;
// Push the layer head of the
// first layer
roots.push(root);
// Define the first layer head
// as the tree root
Node* lyr_root = root;
// Traverse all layers
while (!roots.empty()) {
// get current layer root
Node* n = roots.front();
// Pop element from roots
roots.pop();
if (lyr_root == n) {
// Layer root was also
// the layer head
while (!r.empty()) {
rr.push_back(r.top());
// Pop every element
// from the stack
r.pop();
}
}
while (n) {
if (n->right) {
// Current traversed node
// has right child then
// this root is next layer
if (n == lyr_root) {
lyr_root = n->right;
}
// Push the right child
// to layer roots queue
roots.push(n->right);
}
// Push node to the
// layer stack
r.push(n->data);
n = n->left;
}
}
// Insert all remaining elements
// for the traversal
while (!r.empty()) {
// After all of the layer
// roots traversed check the
// final layer in stack
rr.push_back(r.top());
r.pop();
}
// Return the traversal of nodes
return rr;
}
// Function that builds the binary tree
// from the given string
Node* buildBinaryTree(char* t)
{
Node* root = NULL;
// Using queue to build tree
queue<Node**> q;
int data = 0;
// Stores the status of last
// node to be ignored or not
bool ignore_last = false;
while (*t != '\0') {
int d = *t - '0';
// If the current character
// is a digits then form the
// number of it
if (d >= 0 && d <= 9) {
data *= 10;
data += d;
ignore_last = false;
}
// If the current character
// is N then it is the
// NULL node
else if (*t == 'N') {
data = 0;
q.pop();
ignore_last = true;
}
// If space occurred then
// add the number formed
else if (*t == ' ') {
// If last is ignored
if (!ignore_last) {
// If root node is not NULL
if (root) {
Node** p = q.front();
q.pop();
if (p != NULL) {
*p = newNode(data);
q.push(&((*p)->left));
q.push(&((*p)->right));
}
}
// Else create a new
// root node
else {
root = newNode(data);
q.push(&(root->left));
q.push(&(root->right));
}
data = 0;
}
}
// Increment t
t++;
}
// Return the root node of the tree
return root;
}
// Driver Code
int main()
{
// Given order of nodes
char T[] = "2 7 5 2 6 N 9 N N 5 11 4 N";
// Builds the Binary Tree
Node* root = buildBinaryTree(T);
// Function Call
vector<int> result
= leftBottomTopRightTraversal(root);
// Print the final traversal
for (int i = 0; i < result.size(); ++i) {
cout << result[i] << " ";
}
return 0;
}
2 7 2 5 6 5 11 4 9
Complejidad temporal: O(N)
Espacio auxiliar: O(N)