Dado un árbol binario, la tarea es imprimir todos los Nodes hoja del árbol binario de derecha a izquierda.
Ejemplos:
Input :
1
/ \
2 3
/ \ / \
4 5 6 7
Output : 7 6 5 4
Input :
1
/ \
2 3
/ \ \
4 5 6
/ / \
7 8 9
Output : 9 8 7 4
Enfoque recursivo: recorra el árbol en orden anticipado, procesando primero la raíz, luego el subárbol derecho y luego el subárbol izquierdo y haga lo siguiente:
- Compruebe si la raíz es nula y luego regrese de la función.
- Si es un Node de hoja, imprímalo.
- De lo contrario, verifique si tiene el hijo derecho, si es así, llame recursivamente a la función para el hijo derecho del Node.
- Verifique si tiene un hijo izquierdo, en caso afirmativo, llame recursivamente a la función para el hijo izquierdo del Node.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print leaf nodes from right to left
#include <iostream>
using namespace std;
// A Binary Tree Node
struct Node {
int data;
struct Node *left, *right;
};
// Utility function to create a new tree node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Function to print leaf
// nodes from right to left
void printLeafNodes(Node* root)
{
// If node is null, return
if (!root)
return;
// If node is leaf node, print its data
if (!root->left && !root->right) {
cout << root->data << " ";
return;
}
// If right child exists, check for leaf
// recursively
if (root->right)
printLeafNodes(root->right);
// If left child exists, check for leaf
// recursively
if (root->left)
printLeafNodes(root->left);
}
// 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);
root->left->left->left = newNode(8);
root->right->right->left = newNode(9);
root->left->left->left->right = newNode(10);
printLeafNodes(root);
return 0;
}
Java
// Java program to print leaf nodes from right to left
import java.util.*;
class GFG
{
// A Binary Tree Node
static class Node
{
int data;
Node left, right;
};
// Utility function to create a new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to print leaf
// nodes from right to left
static void printLeafNodes(Node root)
{
// If node is null, return
if (root == null)
return;
// If node is leaf node, print its data
if (root.left == null && root.right == null)
{
System.out.print( root.data +" ");
return;
}
// If right child exists, check for leaf
// recursively
if (root.right != null)
printLeafNodes(root.right);
// If left child exists, check for leaf
// recursively
if (root.left != null)
printLeafNodes(root.left);
}
// 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);
root.left.left.left = newNode(8);
root.right.right.left = newNode(9);
root.left.left.left.right = newNode(10);
printLeafNodes(root);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to print # leaf nodes from right to left # Binary tree node class newNode: def __init__(self, data): self.data = data self.left = None self.right = None # Function to print leaf # nodes from right to left def printLeafNodes(root): # If node is null, return if root == None: return # If node is leaf node, # print its data if (root.left == None and root.right == None): print(root.data, end = " ") return # If right child exists, # check for leaf recursively if root.right: printLeafNodes(root.right) # If left child exists, # check for leaf recursively if root.left: printLeafNodes(root.left) # 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) root.left.left.left = newNode(8) root.right.right.left = newNode(9) root.left.left.left.right = newNode(10) printLeafNodes(root) # This code is contributed by SHUBHAMSINGH10
C#
using System;
// C# program to print leaf nodes from right to left
class GFG
{
// A Binary Tree Node
public class Node
{
public int data;
public Node left, right;
}
// Utility function to create a new tree node
public static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to print leaf
// nodes from right to left
public static void printLeafNodes(Node root)
{
// If node is null, return
if (root == null)
{
return;
}
// If node is leaf node, print its data
if (root.left == null && root.right == null)
{
Console.Write(root.data + " ");
return;
}
// If right child exists, check for leaf
// recursively
if (root.right != null)
{
printLeafNodes(root.right);
}
// If left child exists, check for leaf
// recursively
if (root.left != null)
{
printLeafNodes(root.left);
}
}
// 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);
root.left.left.left = newNode(8);
root.right.right.left = newNode(9);
root.left.left.left.right = newNode(10);
printLeafNodes(root);
}
}
// This code is contributed by shrikanth13
Javascript
<script>
// JavaScript program to print leaf nodes from right to left
// A Binary Tree Node
class Node
{
constructor()
{
this.data = 0;
this.right = null;
this.left = null;
}
}
// Utility function to create a new tree node
function newNode(data)
{
var temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to print leaf
// nodes from right to left
function printLeafNodes(root)
{
// If node is null, return
if (root == null)
{
return;
}
// If node is leaf node, print its data
if (root.left == null && root.right == null)
{
document.write(root.data + " ");
return;
}
// If right child exists, check for leaf
// recursively
if (root.right != null)
{
printLeafNodes(root.right);
}
// If left child exists, check for leaf
// recursively
if (root.left != null)
{
printLeafNodes(root.left);
}
}
// Driver code
var 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);
root.left.left.left = newNode(8);
root.right.right.left = newNode(9);
root.left.left.left.right = newNode(10);
printLeafNodes(root);
</script>
Producción:
9 6 5 10
Enfoque iterativo: la idea es realizar un recorrido iterativo posterior al orden utilizando una pila, pero de una manera modificada, primero, visitaremos el subárbol derecho y luego el subárbol izquierdo y finalmente el Node raíz e imprimiremos los Nodes hoja.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print leaf nodes from
// right to left 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 printLeafRightToLeft(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->right;
}
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
// left subtree as null then pop that node and
// print the node only if its right
// subtree is also null
if (s.top()->left == NULL) {
p = s.top();
s.pop();
// Print the leaf node
if (p->right == NULL)
printf("%d ", p->data);
}
while (p == s.top()->left) {
p = s.top();
s.pop();
if (s.empty())
break;
}
// If stack is not empty then assign p as
// the stack's top node's left child
if (!s.empty())
p = s.top()->left;
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);
printLeafRightToLeft(root);
return 0;
}
Java
// Java program to print leaf nodes from
// right to left using one stack
import java.util.Stack;
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 = node.right = null;
node.data = key;
return node;
}
// Function to Print all the leaf nodes
// of Binary tree using one stack
static void printLeafRightToLeft(Node p)
{
// stack to store the nodes
Stack<Node> s = new Stack<>();
while (true)
{
// If p is not null then push
// it on the stack
if (p != null)
{
s.push(p);
p = p.right;
}
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
// left subtree as null then pop that node and
// print the node only if its right
// subtree is also null
if (s.peek().left == null)
{
p = s.peek();
s.pop();
// Print the leaf node
if (p.right == null)
System.out.print( p.data+" ");
}
while (p == s.peek().left)
{
p = s.peek();
s.pop();
if (s.empty())
break;
}
// If stack is not empty then assign p as
// the stack's top node's left child
if (!s.empty())
p = s.peek().left;
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);
printLeafRightToLeft(root);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to print leaf nodes # from right to left using one stack # Tree node class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Function to create a new node def newNode(key) : node = Node(0) node.left = node.right = None node.data = key return node # Function to Print all the leaf nodes # of Binary tree using one stack def printLeafRightToLeft(p) : # stack to store the nodes s = [] while (True) : # If p is not None then append # it on the stack if (p != None) : s.append(p) p = p.right else: # If stack is len then come out # of the loop if (len(s) == 0) : break else: # If the node on top of the stack has # its left subtree as None then pop # that node and print the node only # if its right subtree is also None if (s[-1].left == None) : p = s[-1] s.pop() # Print the leaf node if (p.right == None) : print( p.data, end = " ") while (p == s[-1].left) : p = s[-1] s.pop() if (len(s) == 0) : break # If stack is not len then assign p as # the stack's top node's left child if (len(s) > 0) : p = s[-1].left 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) printLeafRightToLeft(root) # This code is contributed by Arnab Kundu
C#
// C# program to print leaf nodes from
// right to left 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 = node.right = null;
node.data = key;
return node;
}
// Function to Print all the leaf nodes
// of Binary tree using one stack
static void printLeafRightToLeft(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.right;
}
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
// left subtree as null then pop that node and
// print the node only if its right
// subtree is also null
if (s.Peek().left == null)
{
p = s.Peek();
s.Pop();
// Print the leaf node
if (p.right == null)
Console.Write(p.data + " ");
}
while (p == s.Peek().left)
{
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 left child
if (s.Count != 0)
p = s.Peek().left;
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);
printLeafRightToLeft(root);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to print leaf nodes from
// right to left using one stack
// Structure of binary tree
class Node
{
constructor()
{
this.left = null;
this.right = null;
this.data = 0;
}
};
// Function to create a new node
function newNode(key)
{
var 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
function printLeafRightToLeft(p)
{
// Stack to store the nodes
var s = [];
while (true)
{
// If p is not null then push
// it on the stack
if (p != null)
{
s.push(p);
p = p.right;
}
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 left subtree as null then pop
// that node and print the node only
// if its right subtree is also null
if (s[s.length - 1].left == null)
{
p = s[s.length - 1];
s.pop();
// Print the leaf node
if (p.right == null)
document.write(p.data + " ");
}
while (p == s[s.length - 1].left)
{
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 left child
if (s.length != 0)
p = s[s.length - 1].left;
else
p = null;
}
}
}
}
// Driver Code
var 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);
printLeafRightToLeft(root);
// This code is contributed by rrrtnx
</script>
Producción:
7 6 5 4
Complejidad temporal : O(N), donde N es el número total de Nodes en el árbol binario.
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