Dado un árbol binario, aplanarlo en una lista enlazada. 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.
Ejemplo :
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: Ya se ha discutido un enfoque que utiliza la recursividad en la publicación anterior . En este enfoque, se ha implicado un recorrido de pedido previo del árbol binario usando la pila. En este recorrido, cada vez que se empuja un hijo derecho en la pila, el hijo derecho se iguala al hijo izquierdo y el hijo izquierdo se iguala a NULL. Si el elemento secundario derecho del Node se convierte en NULL, la pila se extrae y el elemento secundario derecho se convierte en el valor extraído de la pila. Los pasos anteriores se repiten hasta que el tamaño de la pila sea cero o la raíz sea NULL.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to flatten the linked
// list using stack | set-2
#include <iostream>
#include <stack>
using namespace std;
struct Node {
int key;
Node *left, *right;
};
/* utility that allocates a new Node
with the given key */
Node* newNode(int key)
{
Node* node = new Node;
node->key = key;
node->left = node->right = NULL;
return (node);
}
// To find the inorder traversal
void inorder(struct Node* root)
{
// base condition
if (root == NULL)
return;
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
// Function to convert binary tree into
// linked list by altering the right node
// and making left node point to NULL
Node* solution(Node* A)
{
// Declare a stack
stack<Node*> st;
Node* ans = A;
// Iterate till the stack is not empty
// and till root is Null
while (A != NULL || st.size() != 0) {
// Check for NULL
if (A->right != NULL) {
st.push(A->right);
}
// Make the Right Left and
// left NULL
A->right = A->left;
A->left = NULL;
// Check for NULL
if (A->right == NULL && st.size() != 0) {
A->right = st.top();
st.pop();
}
// Iterate
A = A->right;
}
return ans;
}
// Driver Code
int main()
{
/* 1
/ \
2 5
/ \ \
3 4 6 */
// Build the tree
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->right->right = newNode(6);
// Call the function to
// flatten the tree
root = solution(root);
cout << "The Inorder traversal after "
"flattening binary tree ";
// call the function to print
// inorder after flattening
inorder(root);
return 0;
return 0;
}
Java
// Java program to flatten the linked
// list using stack | set-2
import java.util.Stack;
class GFG
{
static class Node
{
int key;
Node left, right;
}
/* utility that allocates a new Node
with the given key */
static Node newNode(int key)
{
Node node = new Node();
node.key = key;
node.left = node.right = null;
return (node);
}
// To find the inorder traversal
static void inorder(Node root)
{
// base condition
if (root == null)
return;
inorder(root.left);
System.out.print(root.key + " ");
inorder(root.right);
}
// Function to convert binary tree into
// linked list by altering the right node
// and making left node point to null
static Node solution(Node A)
{
// Declare a stack
Stack<Node> st = new Stack<>();
Node ans = A;
// Iterate till the stack is not empty
// and till root is Null
while (A != null || st.size() != 0)
{
// Check for null
if (A.right != null)
{
st.push(A.right);
}
// Make the Right Left and
// left null
A.right = A.left;
A.left = null;
// Check for null
if (A.right == null && st.size() != 0)
{
A.right = st.peek();
st.pop();
}
// Iterate
A = A.right;
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
/* 1
/ \
2 5
/ \ \
3 4 6 */
// Build the tree
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(5);
root.left.left = newNode(3);
root.left.right = newNode(4);
root.right.right = newNode(6);
// Call the function to
// flatten the tree
root = solution(root);
System.out.print("The Inorder traversal after "
+"flattening binary tree ");
// call the function to print
// inorder after flattening
inorder(root);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to flatten the linked
# list using stack | set-2
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# Utility that allocates a new Node
# with the given key
def newNode(key):
node = Node(key)
node.key = key
node.left = node.right = None
return (node)
# To find the inorder traversal
def inorder(root):
# Base condition
if (root == None):
return
inorder(root.left)
print(root.key, end = ' ')
inorder(root.right)
# Function to convert binary tree into
# linked list by altering the right node
# and making left node point to None
def solution(A):
# Declare a stack
st = []
ans = A
# Iterate till the stack is not empty
# and till root is Null
while (A != None or len(st) != 0):
# Check for None
if (A.right != None):
st.append(A.right)
# Make the Right Left and
# left None
A.right = A.left
A.left = None
# Check for None
if (A.right == None and len(st) != 0):
A.right = st[-1]
st.pop()
# Iterate
A = A.right
return ans
# Driver Code
if __name__=='__main__':
''' 1
/ \
2 5
/ \ \
3 4 6 '''
# Build the tree
root = newNode(1)
root.left = newNode(2)
root.right = newNode(5)
root.left.left = newNode(3)
root.left.right = newNode(4)
root.right.right = newNode(6)
# Call the function to
# flatten the tree
root = solution(root)
print("The Inorder traversal after "
"flattening binary tree ",
end = '')
# Call the function to print
# inorder after flattening
inorder(root)
# This code is contributed by rutvik_56
C#
// C# program to flatten the linked
// list using stack | set-2
using System;
using System.Collections.Generic;
class GFG
{
public class Node
{
public int key;
public Node left, right;
}
/* utility that allocates a new Node
with the given key */
static Node newNode(int key)
{
Node node = new Node();
node.key = key;
node.left = node.right = null;
return (node);
}
// To find the inorder traversal
static void inorder(Node root)
{
// base condition
if (root == null)
return;
inorder(root.left);
Console.Write(root.key + " ");
inorder(root.right);
}
// Function to convert binary tree into
// linked list by altering the right node
// and making left node point to null
static Node solution(Node A)
{
// Declare a stack
Stack<Node> st = new Stack<Node>();
Node ans = A;
// Iterate till the stack is not empty
// and till root is Null
while (A != null || st.Count != 0)
{
// Check for null
if (A.right != null)
{
st.Push(A.right);
}
// Make the Right Left and
// left null
A.right = A.left;
A.left = null;
// Check for null
if (A.right == null && st.Count != 0)
{
A.right = st.Peek();
st.Pop();
}
// Iterate
A = A.right;
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
/* 1
/ \
2 5
/ \ \
3 4 6 */
// Build the tree
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(5);
root.left.left = newNode(3);
root.left.right = newNode(4);
root.right.right = newNode(6);
// Call the function to
// flatten the tree
root = solution(root);
Console.Write("The Inorder traversal after "
+"flattening binary tree ");
// call the function to print
// inorder after flattening
inorder(root);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to flatten the linked
// list using stack | set-2
class Node
{
constructor()
{
this.key = 0;
this.left = null;
this.right = null;
}
}
/* utility that allocates a new Node
with the given key */
function newNode(key)
{
var node = new Node();
node.key = key;
node.left = node.right = null;
return (node);
}
// To find the inorder traversal
function inorder( root)
{
// base condition
if (root == null)
return;
inorder(root.left);
document.write(root.key + " ");
inorder(root.right);
}
// Function to convert binary tree into
// linked list by altering the right node
// and making left node point to null
function solution(A)
{
// Declare a stack
var st = [];
var ans = A;
// Iterate till the stack is not empty
// and till root is Null
while (A != null || st.length != 0)
{
// Check for null
if (A.right != null)
{
st.push(A.right);
}
// Make the Right Left and
// left null
A.right = A.left;
A.left = null;
// Check for null
if (A.right == null && st.length != 0)
{
A.right = st[st.length-1];
st.pop();
}
// Iterate
A = A.right;
}
return ans;
}
// Driver Code
/* 1
/ \
2 5
/ \ \
3 4 6 */
// Build the tree
var root = newNode(1);
root.left = newNode(2);
root.right = newNode(5);
root.left.left = newNode(3);
root.left.right = newNode(4);
root.right.right = newNode(6);
// Call the function to
// flatten the tree
root = solution(root);
document.write("The Inorder traversal after "
+"flattening binary tree ");
// call the function to print
// inorder after flattening
inorder(root);
// This code is contributed by famously.
</script>
Producción:
The Inorder traversal after flattening binary tree 1 2 3 4 5 6
Complejidad temporal: O(N)
Espacio auxiliar: O(Log N)
Publicación traducida automáticamente
Artículo escrito por Chirayu Asati y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA