Вывести все листовые узлы двоичного дерева справа налево

Опубликовано: 23 Января, 2022

Учитывая двоичное дерево, задача состоит в том, чтобы распечатать все листовые узлы двоичного дерева справа налево.

Примеры:

Вход : 
       1
      / 
     2 3
    /  / 
   4 5 6 7
Выход: 7 6 5 4

Вход :
        1
       / 
      2 3
     /  
    4 5 6
        / / 
       7 8 9
Выход: 9 8 7 4

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Рекурсивный подход: просмотрите дерево в режиме предварительного заказа, сначала обработав корень, затем правое поддерево, а затем левое поддерево, и выполните следующие действия:

Убедитесь, что корень равен нулю, а затем вернитесь из функции.
Если это листовой узел, распечатайте его.
Если нет, то проверьте, есть ли у него правый дочерний элемент, если да, то вызовите функцию для правого дочернего элемента узла рекурсивно.
Проверьте, оставил ли он дочерний элемент, если да, то вызовите функцию для левого дочернего элемента узла рекурсивно.

Below is the implementation of the above approach:

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

Output:

9 6 5 10

Структуры данных

Вывести все листовые узлы двоичного дерева справа налево

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C++

Java

Python3

C#

РЕКОМЕНДУЕМЫЕ СТАТЬИ