Dado un árbol binario, aclárelo en una lista enlazada en el lugar. No se permite el uso de estructuras de datos auxiliares. Después de aplanar, la izquierda de cada Node debe apuntar a NULL y la derecha debe contener el siguiente Node en orden de nivel.
Ejemplos:
Input:
1
/ \
2 5
/ \ \
3 4 6
Output:
1
\
2
\
3
\
4
\
5
\
6
Input:
1
/ \
3 4
/
2
\
5
Output:
1
\
3
\
4
\
2
\
5
Enfoque: recurra al árbol binario en formato Inorder, en cada etapa de la llamada a la función, pase la dirección del último Node en la lista enlazada aplanada para que el Node actual pueda convertirse en un Node derecho del último Node.
Para el hijo izquierdo, su Node principal es el último Node en la lista plana.
Para el hijo derecho, hay dos condiciones:
- Si no queda ningún hijo del padre, el Node padre es el último Node en la lista aplanada.
- Si el hijo izquierdo no es nulo, el Node hoja del subárbol izquierdo es el último Node de la lista aplanada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to flatten the binary tree
// using previous node approach
using namespace std;
#include <iostream>
#include <stdlib.h>
// Structure to represent a node of the tree
struct Node {
int data;
struct Node* left;
struct Node* right;
};
Node* AllocNode(int data)
{
Node* temp = new Node;
temp->left = NULL;
temp->right = NULL;
temp->data = data;
return temp;
}
// Utility function to print the inorder
// traversal of the tree
void PrintInorderBinaryTree(Node* root)
{
if (root == NULL)
return;
PrintInorderBinaryTree(root->left);
std::cout << root->data << " ";
PrintInorderBinaryTree(root->right);
}
// Function to make current node right of
// the last node in the list
void FlattenBinaryTree(Node* root, Node** last)
{
if (root == NULL)
return;
Node* left = root->left;
Node* right = root->right;
// Avoid first iteration where root is
// the only node in the list
if (root != *last) {
(*last)->right = root;
(*last)->left = NULL;
*last = root;
}
FlattenBinaryTree(left, last);
FlattenBinaryTree(right, last);
if (left == NULL && right == NULL)
*last = root;
}
// Driver Code
int main()
{
// Build the tree
Node* root = AllocNode(1);
root->left = AllocNode(2);
root->left->left = AllocNode(3);
root->left->right = AllocNode(4);
root->right = AllocNode(5);
root->right->right = AllocNode(6);
// Print the inorder traversal of the
// original tree
std::cout << "Original inorder traversal : ";
PrintInorderBinaryTree(root);
std::cout << std::endl;
// Flatten a binary tree, at the beginning
// root node is the only and last in the list
Node* last = root;
FlattenBinaryTree(root, &last);
// Print the inorder traversal of the flattened
// binary tree
std::cout << "Flattened inorder traversal : ";
PrintInorderBinaryTree(root);
std::cout << std::endl;
return 0;
}
Java
// Java program to flatten the binary tree
// using previous node approach
class GFG
{
// Structure to represent a node of the tree
static class Node
{
int data;
Node left;
Node right;
};
static Node AllocNode(int data)
{
Node temp = new Node();
temp.left = null;
temp.right = null;
temp.data = data;
return temp;
}
// Utility function to print the inorder
// traversal of the tree
static void PrintInorderBinaryTree(Node root)
{
if (root == null)
return;
PrintInorderBinaryTree(root.left);
System.out.print( root.data + " ");
PrintInorderBinaryTree(root.right);
}
static Node last =null;
// Function to make current node right of
// the last node in the list
static void FlattenBinaryTree(Node root)
{
if (root == null)
return;
Node left = root.left;
Node right = root.right;
// Avoid first iteration where root is
// the only node in the list
if (root != last) {
(last).right = root;
(last).left = null;
last = root;
}
FlattenBinaryTree(left);
FlattenBinaryTree(right);
if (left == null && right == null)
last = root;
}
// Driver Code
public static void main(String args[])
{
// Build the tree
Node root = AllocNode(1);
root.left = AllocNode(2);
root.left.left = AllocNode(3);
root.left.right = AllocNode(4);
root.right = AllocNode(5);
root.right.right = AllocNode(6);
// Print the inorder traversal of the
// original tree
System.out.print("Original inorder traversal : ");
PrintInorderBinaryTree(root);
System.out.println();
// Flatten a binary tree, at the beginning
// root node is the only and last in the list
last = root;
FlattenBinaryTree(root);
// Print the inorder traversal of the flattened
// binary tree
System.out.print("Flattened inorder traversal : ");
PrintInorderBinaryTree(root);
System.out.println();
}
}
// This code is contributed by Arnab Kundu
Python
# Python program to flatten binary tree
# using previous node approach
# Node class to represent a node of the tree
class Node:
def __init__(self, data):
self.data = data
self.right = None
self.left = None
# Utility function to print the inorder
# traversal of the tree
def PrintInorderBinaryTree(root):
if(root == None):
return
PrintInorderBinaryTree(root.left)
print(str(root.data), end = " ")
PrintInorderBinaryTree(root.right)
# Function to make current node right of
# the last node in the list
def FlattenBinaryTree(root):
# A global variable which maintains the last node
# that was added to the linked list
global last
if(root == None):
return
left = root.left
right = root.right
# Avoid first iteration where root is
# the only node in the list
if(root != last):
last.right = root
last.left = None
last = root
FlattenBinaryTree(left)
FlattenBinaryTree(right)
if(left == None and right == None):
last = root
# Build the tree
root = Node(1)
root.left = Node(2)
root.left.left = Node(3)
root.left.right = Node(4)
root.right = Node(5)
root.right.right = Node(6)
# Print the inorder traversal of the
# original tree
print("Original inorder traversal : ", end = "")
PrintInorderBinaryTree(root)
print("")
# Global variable to maintain the
# last node added to the linked list
last = root
# Flatten the binary tree, at the beginning
# root node is the only node in the list
FlattenBinaryTree(root)
# Print the inorder traversal of the flattened
# binary tree
print("Flattened inorder traversal : ", end = "")
PrintInorderBinaryTree(root)
# This code is contributed by Pranav Devarakonda
C#
// C# program to flatten the binary tree
// using previous node approach
using System;
class GFG
{
// Structure to represent a node of the tree
public class Node
{
public int data;
public Node left;
public Node right;
};
static Node AllocNode(int data)
{
Node temp = new Node();
temp.left = null;
temp.right = null;
temp.data = data;
return temp;
}
// Utility function to print the inorder
// traversal of the tree
static void PrintInorderBinaryTree(Node root)
{
if (root == null)
return;
PrintInorderBinaryTree(root.left);
Console.Write(root.data + " ");
PrintInorderBinaryTree(root.right);
}
static Node last =null;
// Function to make current node right of
// the last node in the list
static void FlattenBinaryTree(Node root)
{
if (root == null)
return;
Node left = root.left;
Node right = root.right;
// Avoid first iteration where root is
// the only node in the list
if (root != last)
{
(last).right = root;
(last).left = null;
last = root;
}
FlattenBinaryTree(left);
FlattenBinaryTree(right);
if (left == null && right == null)
last = root;
}
// Driver Code
public static void Main(String []args)
{
// Build the tree
Node root = AllocNode(1);
root.left = AllocNode(2);
root.left.left = AllocNode(3);
root.left.right = AllocNode(4);
root.right = AllocNode(5);
root.right.right = AllocNode(6);
// Print the inorder traversal of the
// original tree
Console.Write("Original inorder traversal : ");
PrintInorderBinaryTree(root);
Console.WriteLine();
// Flatten a binary tree, at the beginning
// root node is the only and last in the list
last = root;
FlattenBinaryTree(root);
// Print the inorder traversal of the flattened
// binary tree
Console.Write("Flattened inorder traversal : ");
PrintInorderBinaryTree(root);
Console.WriteLine();
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to flatten the binary tree
// using previous node approach
// Structure to represent a node of the tree
class Node {
constructor() {
this.data = 0;
this.left = null;
this.right = null;
}
}
function AllocNode( data)
{
var temp = new Node();
temp.left = null;
temp.right = null;
temp.data = data;
return temp;
}
// Utility function to print the inorder
// traversal of the tree
function PrintInorderBinaryTree( root)
{
if (root == null)
return;
PrintInorderBinaryTree(root.left);
document.write( root.data + " ");
PrintInorderBinaryTree(root.right);
}
var last =null;
// Function to make current node right of
// the last node in the list
function FlattenBinaryTree( root)
{
if (root == null)
return;
var left = root.left;
var right = root.right;
// Avoid first iteration where root is
// the only node in the list
if (root != last) {
(last).right = root;
(last).left = null;
last = root;
}
FlattenBinaryTree(left);
FlattenBinaryTree(right);
if (left == null && right == null)
last = root;
}
// Driver Code
// Build the tree
var root = AllocNode(1);
root.left = AllocNode(2);
root.left.left = AllocNode(3);
root.left.right = AllocNode(4);
root.right = AllocNode(5);
root.right.right = AllocNode(6);
// Print the inorder traversal of the
// original tree
document.write("Original inorder traversal : ");
PrintInorderBinaryTree(root);
document.write("</br>");
// Flatten a binary tree, at the beginning
// root node is the only and last in the list
last = root;
FlattenBinaryTree(root);
// Print the inorder traversal of the flattened
// binary tree
document.write("Flattened inorder traversal : ");
PrintInorderBinaryTree(root);
document.write("</br>");
// This code is contributed by JANA_SAYANTAN.
</script>
Producción:
Original inorder traversal : 3 2 4 1 5 6 Flattened inorder traversal : 1 2 3 4 5 6