Dado un árbol binario, la tarea es imprimir todos los Nodes hoja del árbol binario dado de izquierda a derecha. Es decir, los Nodes deben imprimirse en el orden en que aparecen de izquierda a derecha en el árbol dado.
Ejemplos:
Input : 1 / \ 2 3 / \ / \ 4 5 6 7 Output : 4 5 6 7 Input : 4 / \ 5 9 / \ / \ 8 3 7 2 / / \ 12 6 1 Output : 12 3 7 6 1
Ya hemos discutido el enfoque iterativo usando dos pilas.
Enfoque: la idea es realizar un recorrido iterativo posterior al pedido utilizando una pila e imprimir los Nodes hoja.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print leaf nodes from // left to right using one stack #include <bits/stdc++.h> using namespace std; // Structure of binary tree struct Node { Node* left; Node* right; int data; }; // Function to create a new node Node* newNode(int key) { Node* node = new Node(); node->left = node->right = NULL; node->data = key; return node; } // Function to Print all the leaf nodes // of Binary tree using one stack void printLeafLeftToRight(Node* p) { // stack to store the nodes stack<Node*> s; while (1) { // If p is not null then push // it on the stack if (p) { s.push(p); p = p->left; } else { // If stack is empty then come out // of the loop if (s.empty()) break; else { // If the node on top of the stack has its // right subtree as null then pop that node and // print the node only if its left // subtree is also null if (s.top()->right == NULL) { p = s.top(); s.pop(); // Print the leaf node if (p->left == NULL) printf("%d ", p->data); } while (p == s.top()->right) { p = s.top(); s.pop(); if (s.empty()) break; } // If stack is not empty then assign p as // the stack's top node's right child if (!s.empty()) p = s.top()->right; else p = NULL; } } } } // Driver Code int main() { Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); printLeafLeftToRight(root); return 0; }
Java
// Java program to print leaf nodes from // left to{ right using one stack import java.util.*; class GfG { // Structure of binary tree static class Node { Node left; Node right; int data; } // Function to create a new node static Node newNode(int key) { Node node = new Node(); node.left = null; node.right = null; node.data = key; return node; } // Function to Print all the leaf nodes // of Binary tree using one stack static void printLeafLeftToRight(Node p) { // stack to store the nodes Stack<Node> s = new Stack<Node> (); while (true) { // If p is not null then push // it on the stack if (p != null) { s.push(p); p = p.left; } else { // If stack is empty then come out // of the loop if (s.isEmpty()) break; else { // If the node on top of the stack has its // right subtree as null then pop that node and // print the node only if its left // subtree is also null if (s.peek().right == null) { p = s.peek(); s.pop(); // Print the leaf node if (p.left == null) System.out.print(p.data + " "); } while (p == s.peek().right) { p = s.peek(); s.pop(); if (s.isEmpty()) break; } // If stack is not empty then assign p as // the stack's top node's right child if (!s.isEmpty()) p = s.peek().right; else p = null; } } } } // Driver Code public static void main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); printLeafLeftToRight(root); } } // This code is contributed by Prerna Saini
Python3
# Python3 program to print leaf nodes from # left to right using one stack # Binary tree node class newNode: def __init__(self, data): self.data = data self.left = None self.right = None # Function to Print all the leaf nodes # of Binary tree using one stack def printLeafLeftToRight(p): # stack to store the nodes s = [] while (1): # If p is not None then push # it on the stack if (p): s.insert(0, p) p = p.left else: # If stack is empty then come out # of the loop if len(s) == 0: break else: # If the node on top of the stack has its # right subtree as None then pop that node # and print the node only if its left # subtree is also None if (s[0].right == None): p = s[0] s.pop(0) # Print the leaf node if (p.left == None): print(p.data, end = " ") while (p == s[0].right): p = s[0] s.pop(0) if len(s) == 0: break # If stack is not empty then assign p as # the stack's top node's right child if len(s): p = s[0].right else: p = None # Driver Code root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) root.right.left = newNode(6) root.right.right = newNode(7) printLeafLeftToRight(root) # This code is contributed by SHUBHAMSINGH10
C#
// C# program to print leaf nodes from // left to{ right using one stack using System; using System.Collections.Generic; class GfG { // Structure of binary tree public class Node { public Node left; public Node right; public int data; } // Function to create a new node static Node newNode(int key) { Node node = new Node(); node.left = null; node.right = null; node.data = key; return node; } // Function to Print all the leaf nodes // of Binary tree using one stack static void printLeafLeftToRight(Node p) { // stack to store the nodes Stack<Node> s = new Stack<Node> (); while (true) { // If p is not null then push // it on the stack if (p != null) { s.Push(p); p = p.left; } else { // If stack is empty then come out // of the loop if (s.Count == 0) break; else { // If the node on top of the stack has its // right subtree as null then pop that node and // print the node only if its left // subtree is also null if (s.Peek().right == null) { p = s.Peek(); s.Pop(); // Print the leaf node if (p.left == null) Console.Write(p.data + " "); } while (p == s.Peek().right) { p = s.Peek(); s.Pop(); if (s.Count == 0) break; } // If stack is not empty then assign p as // the stack's top node's right child if (s.Count != 0) p = s.Peek().right; else p = null; } } } } // Driver Code public static void Main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); printLeafLeftToRight(root); } } // This code has been contributed by 29AjayKumar
Javascript
<script> // JavaScript program to print leaf nodes from // left to{ right using one stack // Structure of binary tree class Node { constructor(key) { this.left = null; this.right = null; this.data = key; } } // Function to create a new node function newNode(key) { let node = new Node(key); return node; } // Function to Print all the leaf nodes // of Binary tree using one stack function printLeafLeftToRight(p) { // stack to store the nodes let s = []; while (true) { // If p is not null then push // it on the stack if (p != null) { s.push(p); p = p.left; } else { // If stack is empty then come out // of the loop if (s.length == 0) break; else { // If the node on top of the stack has its // right subtree as null then pop that node and // print the node only if its left // subtree is also null if (s[s.length - 1].right == null) { p = s[s.length - 1]; s.pop(); // Print the leaf node if (p.left == null) document.write(p.data + " "); } while (p == s[s.length - 1].right) { p = s[s.length - 1]; s.pop(); if (s.length == 0) break; } // If stack is not empty then assign p as // the stack's top node's right child if (s.length != 0) p = s[s.length - 1].right; else p = null; } } } } let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); printLeafLeftToRight(root); </script>
Producción:
4 5 6 7
Complejidad temporal : O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA