Свести двоичное дерево в порядке обхода пост-заказа

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

Учитывая двоичное дерево, задача состоит в том, чтобы сгладить его в порядке его обхода после упорядочения. В уплощенном двоичном дереве левый узел всех узлов должен быть ПУСТО (NULL).

Примеры:

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

Вход:
      1
       
        2
         
          3
           
            4
             
              5
Выход: 5 4 3 2 1

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

Простым подходом будет воссоздание двоичного дерева из его обхода после заказа. Это займет O (N) дополнительного места, если N - количество узлов в BST.

Лучшее решение - смоделировать обход данного двоичного дерева после заказа.

Создайте фиктивный узел.
Создайте переменную с именем «prev» и сделайте так, чтобы она указывала на фиктивный узел.
Выполняйте обход постзаказа и на каждом шаге.
- Установить предыдущий -> правый = текущий
- Установить предыдущий -> слева = NULL
- Установить prev = curr

Это улучшит сложность пространства до O (H) в худшем случае, поскольку обход после заказа занимает O (H) дополнительного пространства.

Below is the implementation of the above approach:

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 the flattened
// binary Tree
void print(node* parent)
{
    node* curr = parent;
    while (curr != NULL)
        cout << curr->data << " ", curr = curr->right;
}
  
// Function to perform post-order traversal
// recursively
void postorder(node* curr, node*& prev)
{
    // Base case
    if (curr == NULL)
        return;
    postorder(curr->left, prev);
    postorder(curr->right, prev);
    prev->left = NULL;
    prev->right = curr;
    prev = curr;
}
  
// Function to flatten the given binary tree
// using post order traversal
node* flatten(node* parent)
{
    // Dummy node
    node* dummy = new node(-1);
  
    // Pointer to previous element
    node* prev = dummy;
  
    // Calling post-order traversal
    postorder(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);
  
    print(flatten(root));
  
    return 0;
}

Java

// Java implementation of the approach
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;
    }
};
static node prev;
  
// Function to print the flattened
// binary Tree
static void print(node parent)
{
    node curr = parent;
    while (curr != null)
    {
        System.out.print(curr.data + " ");
        curr = curr.right;
    }
}
  
// Function to perform post-order traversal
// recursively
static void postorder(node curr)
{
    // Base case
    if (curr == null)
        return;
    postorder(curr.left);
    postorder(curr.right);
    prev.left = null;
    prev.right = curr;
    prev = curr;
}
  
// Function to flatten the given binary tree
// using post order traversal
static node flatten(node parent)
{
    // Dummy node
    node dummy = new node(-1);
  
    // Pointer to previous element
    prev = dummy;
  
    // Calling post-order traversal
    postorder(parent);
  
    prev.left = null;
    prev.right = null;
    node ret = dummy.right;
  
    // Delete dummy node
    dummy = null;
    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);
  
    print(flatten(root));
}
} 
  
// This code is contributed by PrinciRaj1992

Python

# Python implementation of above algorithm
  
# Utility class to create a node 
class node: 
    def __init__(self, key): 
        self.data = key 
        self.left = self.right = None
  
# Function to print the flattened
# binary Tree
def print_(parent):
  
    curr = parent
    while (curr != None):
        print( curr.data ,end = " ")
        curr = curr.right
  
prev = None
  
# Function to perform post-order traversal
# recursively
def postorder( curr ):
      
    global prev
      
    # Base case
    if (curr == None):
        return
    postorder(curr.left)
    postorder(curr.right)
    prev.left = None
    prev.right = curr
    prev = curr
  
# Function to flatten the given binary tree
# using post order traversal
def flatten(parent):
  
    global prev
      
    # Dummy node
    dummy = node(-1)
  
    # Pointer to previous element
    prev = dummy
  
    # Calling post-order traversal
    postorder(parent)
  
    prev.left = None
    prev.right = None
    ret = dummy.right
  
    return ret
  
# Driver code
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)
  
print_(flatten(root))
  
  
# This code is contributed by Arnab Kundu

C#

// C# implementation of the approach
using System;
  
class GFG
{
  
// 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;
    }
};
static node prev;
  
// Function to print the flattened
// binary Tree
static void print(node parent)
{
    node curr = parent;
    while (curr != null)
    {
        Console.Write(curr.data + " ");
        curr = curr.right;
    }
}
  
// Function to perform post-order traversal
// recursively
static void postorder(node curr)
{
    // Base case
    if (curr == null)
        return;
    postorder(curr.left);
    postorder(curr.right);
    prev.left = null;
    prev.right = curr;
    prev = curr;
}
  
// Function to flatten the given binary tree
// using post order traversal
static node flatten(node parent)
{
    // Dummy node
    node dummy = new node(-1);
  
    // Pointer to previous element
    prev = dummy;
  
    // Calling post-order traversal
    postorder(parent);
  
    prev.left = null;
    prev.right = null;
    node ret = dummy.right;
  
    // Delete dummy node
    dummy = null;
    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);
  
    print(flatten(root));
}
}
  
// This code is contributed by Princi Singh

Output:

2 4 3 6 8 7 5

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

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

Свести двоичное дерево в порядке обхода пост-заказа

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

C++

Java

Python

C#

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