Dado un árbol de búsqueda binario, la tarea es aplanarlo en una lista ordenada. Precisamente, el valor de cada Node debe ser menor que los valores de todos los Nodes a su derecha, y su Node izquierdo debe ser NULL después del aplanamiento. Debemos hacerlo en O(H) espacio extra donde ‘H’ es la altura de BST.
Ejemplos:
Input: 5 / \ 3 7 / \ / \ 2 4 6 8 Output: 2 3 4 5 6 7 8
Input: 1 \ 2 \ 3 \ 4 \ 5 Output: 1 2 3 4 5
Enfoque: un enfoque simple será recrear el BST a partir de su recorrido en orden . Esto tomará O(N) espacio extra donde N es el número de Nodes en BST.
Para mejorar eso, simularemos el recorrido en orden de un árbol binario de la siguiente manera:
- Cree un Node ficticio.
- Cree una variable llamada ‘prev’ y haga que apunte al Node ficticio.
- Realice un recorrido en orden y en cada paso.
- Establecer anterior -> derecha = actual
- Establecer anterior -> izquierda = NULL
- Establecer anterior = actual
Esto mejorará la complejidad del espacio a O(H) en el peor de los casos, ya que el recorrido en orden requiere espacio adicional de O(H).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Node of the binary tree struct node { int data; node* left; node* right; node(int data) { this->data = data; left = NULL; right = NULL; } }; // Function to print flattened // binary Tree void print(node* parent) { node* curr = parent; while (curr != NULL) cout << curr->data << " ", curr = curr->right; } // Function to perform in-order traversal // recursively void inorder(node* curr, node*& prev) { // Base case if (curr == NULL) return; inorder(curr->left, prev); prev->left = NULL; prev->right = curr; prev = curr; inorder(curr->right, prev); } // Function to flatten binary tree using // level order traversal node* flatten(node* parent) { // Dummy node node* dummy = new node(-1); // Pointer to previous element node* prev = dummy; // Calling in-order traversal inorder(parent, prev); prev->left = NULL; prev->right = NULL; node* ret = dummy->right; // Delete dummy node delete dummy; return ret; } // Driver code int main() { node* root = new node(5); root->left = new node(3); root->right = new node(7); root->left->left = new node(2); root->left->right = new node(4); root->right->left = new node(6); root->right->right = new node(8); // Calling required function print(flatten(root)); return 0; }
Java
// Java implementation of the // above approach import java.util.*; class GFG{ // Node of the binary tree static class node { int data; node left; node right; node(int data) { this.data = data; left = null; right = null; } }; // Function to print flattened // binary tree static void print(node parent) { node curr = parent; while (curr != null) { System.out.print(curr.data + " "); curr = curr.right; } } static node prev; // Function to perform // in-order traversal static void Inorder(node curr) { // Base case if (curr == null) return; Inorder(curr.left); prev.left = null; prev.right = curr; prev = curr; Inorder(curr.right); } // Function to flatten binary // tree using level order // traversal static node flatten(node parent) { // Dummy node node dummy = new node(-1); // Pointer to previous // element prev = dummy; // Calling in-order // traversal Inorder(parent); prev.left = null; prev.right = null; node ret = dummy.right; // Delete dummy node //delete dummy; return ret; } // Driver code public static void main(String[] args) { node root = new node(5); root.left = new node(3); root.right = new node(7); root.left.left = new node(2); root.left.right = new node(4); root.right.left = new node(6); root.right.right = new node(8); // Calling required function print(flatten(root)); } } // This code is contributed by Debojyoti Mandal
C#
// C# implementation of the // above approach using System; public class Program{ // Node of the binary tree public class node { public int data; public node left; public node right; public node(int data) { this.data = data; left = null; right = null; } }; // Function to print flattened // binary tree static void print(node parent) { node curr = parent; while (curr != null) { Console.Write(curr.data + " "); curr = curr.right; } } static node prev; // Function to perform // in-order traversal static void Inorder(node curr) { // Base case if (curr == null) return; Inorder(curr.left); prev.left = null; prev.right = curr; prev = curr; Inorder(curr.right); } // Function to flatten binary // tree using level order // traversal static node flatten(node parent) { // Dummy node node dummy = new node(-1); // Pointer to previous // element prev = dummy; // Calling in-order // traversal Inorder(parent); prev.left = null; prev.right = null; node ret = dummy.right; // Delete dummy node //delete dummy; return ret; } // Driver code public static void Main(string[] args) { node root = new node(5); root.left = new node(3); root.right = new node(7); root.left.left = new node(2); root.left.right = new node(4); root.right.left = new node(6); root.right.right = new node(8); // Calling required function print(flatten(root)); } } // This code is contributed by rrrtnx.
Javascript
<script> // Javascript implementation of the approach // Node of the binary tree class node { constructor(data) { this.left = null; this.right = null; this.data = data; } } let prev; // Function to print flattened // binary Tree function print(parent) { let curr = parent; while (curr != null) { document.write(curr.data + " "); curr = curr.right; } } // Function to perform in-order traversal // recursively function inorder(curr) { // Base case if (curr == null) return; inorder(curr.left); prev.left = null; prev.right = curr; prev = curr; inorder(curr.right); } // Function to flatten binary tree using // level order traversal function flatten(parent) { // Dummy node let dummy = new node(-1); // Pointer to previous element prev = dummy; // Calling in-order traversal inorder(parent); prev.left = null; prev.right = null; let ret = dummy.right; // Delete dummy node return ret; } // Driver code let root = new node(5); root.left = new node(3); root.right = new node(7); root.left.left = new node(2); root.left.right = new node(4); root.right.left = new node(6); root.right.right = new node(8); // Calling required function print(flatten(root)); // This code is contributed by divyeshrabadiya07 </script>
Python3
# Python3 implementation of the approach global prev # Node of the binary tree class node : def __init__(self, data): self.data = data self.left = None self.right = None # Function to print flattened # binary Tree def printTree(parent): curr = parent while (curr != None): print(curr.data,end=' ') curr = curr.right # Function to perform in-order traversal # recursively def inorder(curr): global prev # Base case if (curr == None): return inorder(curr.left) prev.left = None prev.right = curr prev = curr inorder(curr.right) # Function to flatten binary tree using # level order traversal def flatten(parent): global prev # Dummy node dummy = node(-1) # Pointer to previous element prev = dummy # Calling in-order traversal inorder(parent) prev.left = None prev.right = None ret = dummy.right # Delete dummy node return ret # Driver code if __name__ == '__main__': root = node(5) root.left = node(3) root.right = node(7) root.left.left = node(2) root.left.right = node(4) root.right.left = node(6) root.right.right = node(8) # Calling required function printTree(flatten(root))
2 3 4 5 6 7 8
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(H)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA