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

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

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

Примеры:

Вход : 
         1
        / 
       2 3
      / / 
     4 5 6
    / / 
   7 8 9
Выход: 1 2 6 7
Выведите крайний правый узел 1-го уровня: 1
Выведите крайний левый узел на 2-м уровне: 2
Выведите крайний правый узел на 3-м уровне: 6
Выведите крайний левый узел на 4-м уровне: 7
Другой возможный вывод будет -> 1 3 4 9

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

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

Мы уже обсуждали итерационный подход к решению этой проблемы. В этом посте обсуждается рекурсивный подход.

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

Below is the implementation of the above approach:

C++

// C++ program to print nodes of extreme corners
// of each level in alternate order
  
#include <bits/stdc++.h>
using namespace std;
  
// A binary tree node
struct Node {
    int data;
    Node *left, *right;
};
  
// Utility function to allocate memory for a new node
Node* newNode(int data)
{
    Node* node = new (Node);
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
  
// Function that returns the height of the binary tree
int height(Node* root)
{
    if (root == NULL)
        return 0;
  
    int lheight = height(root->left);
    int rheight = height(root->right);
  
    return max(lheight, rheight) + 1;
}
  
// Function performs level order traversal from right to
// left and prints the first node during the traversal
void rightToLeft(Node* root, int level, int& f)
{
    if (root == NULL)
        return;
  
    // Checks for the value of f so that
    // only first node is printed during
    // the traversal and no other node is printed
    if (level == 1 && f == 0) {
        printf("%d ", root->data);
        f = 1;
    }
  
    else if (level > 1) {
        rightToLeft(root->right, level - 1, f);
        rightToLeft(root->left, level - 1, f);
    }
}
  
// Function performs level order traversal from left to
// right and prints the first node during the traversal
void leftToRight(Node* root, int level, int& f)
{
    if (root == NULL)
        return;
  
    // Checks for the value of f so that
    // only first node is printed during
    // the traversal and no other node is printed
    if (level == 1 && f == 1) {
        printf("%d ", root->data);
        f = 0;
    }
  
    else if (level > 1) {
        leftToRight(root->left, level - 1, f);
        leftToRight(root->right, level - 1, f);
    }
}
  
// Function to print the extreme nodes of
// a given binary tree
void printExtremeNodes(Node* root)
{
    // Stores height of binary tree
    int h = height(root);
  
    // Flag to mark the change in level
    int flag = 0;
  
    // To check if the extreme node of a
    // particular level has been visited
    int f = 0;
  
    for (int i = 1; i <= h; i++) {
        // If flag is zero then traverse from
        // right to left at the given level and
        // print the first node during the traversal
        if (flag == 0) {
            rightToLeft(root, i, f);
            flag = 1;
        }
  
        // If flag is one then traverse from
        // left to right at the given level and
        // print the first node during the traversal
        else if (flag == 1) {
            leftToRight(root, i, f);
            flag = 0;
        }
    }
  
    return;
}
  
// 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->right = newNode(7);
  
    root->left->left->left = newNode(8);
    root->left->left->right = newNode(9);
    root->left->right->left = newNode(10);
    root->left->right->right = newNode(11);
    root->right->right->left = newNode(14);
    root->right->right->right = newNode(15);
  
    root->left->left->left->left = newNode(16);
    root->left->left->left->right = newNode(17);
    root->right->right->right->right = newNode(31);
  
    printExtremeNodes(root);
  
    return 0;
}

Java

// Java program to print nodes of extreme corners 
// of each level in alternate order 
import java.util.*;
  
class GFG
{
      
//INT class
static class INT
{
    int a;
}
  
// A binary tree node 
static class Node 
{ 
    int data; 
    Node left, right; 
}; 
  
// Utility function to allocate memory for a new node 
static Node newNode(int data) 
{ 
    Node node = new Node(); 
    node.data = data; 
    node.left = node.right = null; 
    return (node); 
} 
  
// Function that returns the height of the binary tree 
static int height(Node root) 
{ 
    if (root == null) 
        return 0; 
  
    int lheight = height(root.left); 
    int rheight = height(root.right); 
  
    return Math.max(lheight, rheight) + 1; 
} 
  
// Function performs level order traversal from right to 
// left and prints the first node during the traversal 
static void rightToLeft(Node root, int level, INT f) 
{ 
    if (root == null) 
        return; 
  
    // Checks for the value of f so that 
    // only first node is printed during 
    // the traversal and no other node is printed 
    if (level == 1 && f.a == 0) 
    { 
        System.out.printf("%d ", root.data); 
        f.a = 1; 
    } 
  
    else if (level > 1) 
    { 
        rightToLeft(root.right, level - 1, f); 
        rightToLeft(root.left, level - 1, f); 
    } 
} 
  
// Function performs level order traversal from left to 
// right and prints the first node during the traversal 
static void leftToRight(Node root, int level, INT f) 
{ 
    if (root == null) 
        return; 
  
    // Checks for the value of f so that 
    // only first node is printed during 
    // the traversal and no other node is printed 
    if (level == 1 && f.a == 1) 
    { 
        System.out.printf("%d ", root.data); 
        f.a = 0; 
    } 
  
    else if (level > 1)
    { 
        leftToRight(root.left, level - 1, f); 
        leftToRight(root.right, level - 1, f); 
    } 
} 
  
// Function to print the extreme nodes of 
// a given binary tree 
static void printExtremeNodes(Node root) 
{ 
    // Stores height of binary tree 
    int h = height(root); 
  
    // Flag to mark the change in level 
    int flag = 0; 
  
    // To check if the extreme node of a 
    // particular level has been visited 
    INT f=new INT();
    f.a = 0; 
  
    for (int i = 1; i <= h; i++) 
    { 
        // If flag is zero then traverse from 
        // right to left at the given level and 
        // print the first node during the traversal 
        if (flag == 0)
        { 
            rightToLeft(root, i, f); 
            flag = 1; 
        } 
  
        // If flag is one then traverse from 
        // left to right at the given level and 
        // print the first node during the traversal 
        else if (flag == 1) 
        { 
            leftToRight(root, i, f); 
            flag = 0; 
        } 
    } 
  
    return; 
} 
  
// 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.right = newNode(7); 
  
    root.left.left.left = newNode(8); 
    root.left.left.right = newNode(9); 
    root.left.right.left = newNode(10); 
    root.left.right.right = newNode(11); 
    root.right.right.left = newNode(14); 
    root.right.right.right = newNode(15); 
  
    root.left.left.left.left = newNode(16); 
    root.left.left.left.right = newNode(17); 
    root.right.right.right.right = newNode(31); 
  
    printExtremeNodes(root); 
  
} 
}
  
// This code is contributed by Arnab Kundu

Python3

# Python3 program to print nodes of 
# extreme corners of each level in 
# alternate order
from collections import deque
  
# A binary tree node has key, pointer to left
# child and a pointer to right child
class Node:
    def __init__(self, key):
          
        self.data = key
        self.left = None
        self.right = None
  
# Function that returns the height of
# the binary tree
def height(root: Node) -> int:
  
    if (root is None):
        return 0
  
    lheight = height(root.left)
    rheight = height(root.right)
  
    return max(lheight, rheight) + 1
  
# Function performs level order traversal 
# from right to left and prints the first
# node during the traversal
def rightToLeft(root: Node, level: int) -> int:
      
    global f
  
    if (root is None):
        return
  
    # Checks for the value of f so that
    # only first node is printed during
    # the traversal and no other node is printed
    if (level == 1 and f == 0):
        print("%d " % root.data, end = "")
        f = 1
  
    elif (level > 1):
        rightToLeft(root.right, level - 1)
        rightToLeft(root.left, level - 1)
  
# Function performs level order traversal 
# from left to right and prints the first 
# node during the traversal
def leftToRight(root: Node, level: int):
      
    global f
  
    if (root is None):
        return
  
    # Checks for the value of f so that
    # only first node is printed during
    # the traversal and no other node is printed
    if (level == 1 and f == 1):
        print("%d " % root.data, end = "")
        f = 0
  
    elif (level > 1):
        leftToRight(root.left, level - 1)
        leftToRight(root.right, level - 1)
  
# Function to print the extreme nodes of
# a given binary tree
def printExtremeNodes(root: Node):
      
    global f
  
    # Stores height of binary tree
    h = height(root)
  
    # Flag to mark the change in level
    flag = 0
  
    # To check if the extreme node of a
    # particular level has been visited
    f = 0
  
    for i in range(1, h + 1):
          
        # If flag is zero then traverse from
        # right to left at the given level and
        # print the first node during the traversal
        if (flag == 0):
            rightToLeft(root, i)
            flag = 1
  
        # If flag is one then traverse from
        # left to right at the given level and
        # print the first node during the traversal
        elif (flag == 1):
     &nbs
Структуры данных

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

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022