Dados dos árboles binarios , la tarea es imprimir los elementos de ambos árboles binarios en orden no decreciente.
Ejemplos:
Entrada: árboles en la imagen de abajo
Salida: 1 2 3 4 5 6
Explicación: Los Nodes en el primer y segundo árbol binario son {3, 1, 5} y {4, 2, 6} respectivamente. Al fusionar y ordenar las dos arrays, la array requerida se convierte en {1, 2, 3, 4, 5, 6}, que es la respuesta requerida.Entrada: árboles en la imagen de abajo
Salida: 0 1 2 3 5 8 10
Enfoque: El problema dado se puede resolver siguiendo los siguientes pasos:
- Cree un mapa para almacenar cada elemento presente en ambos árboles junto con sus frecuencias.
- Recorre el primer árbol e inserta cada elemento con su frecuencia en el mapa.
- De manera similar, recorra el primer árbol e inserte cada elemento con su frecuencia en el mapa.
- Recorre el mapa e imprime todos los elementos, sus tiempos de frecuencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a binary tree node
class node {
public:
int data;
node* left;
node* right;
};
// Helper function that allocates
// a new node with the given data
node* newNode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return (Node);
}
// Map to store all elements
// from given two trees
map<int, int> m;
// Recursive function to perform
// inorder traversal on tree
void traverse(node* root)
{
// Base Case
if (root == NULL)
return;
else {
// Update map
m[root->data]++;
}
// Recursive call for left subtree
traverse(root->left);
// Recursive call for right subtree
traverse(root->right);
}
// Function to print all the elements of
// two given binary trees in sorted order
void printAllElements(node* root1, node* root2)
{
// Traverse the 1st tree
traverse(root1);
// Traverse the 2nd tree
traverse(root2);
// Traverse the map
for (auto it : m) {
// Print current element
// its frequency times
for (int i = 0; i < it.second; i++) {
cout << it.first << " ";
}
}
}
// Driver code
int main()
{
node* root1 = newNode(8);
root1->left = newNode(2);
root1->right = newNode(10);
root1->left->left = newNode(1);
node* root2 = newNode(5);
root2->left = newNode(3);
root2->right = newNode(0);
printAllElements(root1, root2);
return 0;
}
Java
// Java program of the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
// Structure of a binary tree node
public class GFG{
public static class Node {
int data;
Node left, right;
Node(int data)
{
left=right=null;
this.data=data;
}
}
// Map to store all elements
// from given two trees
public static Map<Integer, Integer> m = new HashMap<>();
// Recursive function to perform
// inorder traversal on tree
public static void traverse(Node root)
{
// Base Case
if (root == null)
return;
else {
// Update map
if(m.containsKey(root.data))
m.put(root.data,m.get(root.data)+1);
else
m.put(root.data,1);
}
// Recursive call for left subtree
traverse(root.left);
// Recursive call for right subtree
traverse(root.right);
}
// Function to print all the elements of
// two given binary trees in sorted order
public static void printAllElements(Node root1, Node root2)
{
// Traverse the 1st tree
traverse(root1);
// Traverse the 2nd tree
traverse(root2);
// Traverse the map
for (Map.Entry<Integer,Integer> it : m.entrySet()) {
// Print current element
// its frequency times
for (int i = 0; i < it.getValue(); i++) {
System.out.print(it.getKey()+" ");
}
}
}
// Driver code
public static void main(String[] args)
{
Node root1 = new Node(8);
root1.left = new Node(2);
root1.right = new Node(10);
root1.left.left = new Node(1);
Node root2 = new Node(5);
root2.left = new Node(3);
root2.right = new Node(0);
printAllElements(root1, root2);
}
}
// This code is contributed by Pushpesh raj.
Python3
# Python code for the above approach
# Structure of a binary tree node
class node:
def __init__(self, d):
self.data = d
self.left = None
self.right = None
# Map to store all elements
# from given two trees
m = {}
# Recursive function to perform
# inorder traversal on tree
def traverse(root):
# Base Case
if (root == None):
return
else:
# Update map
if (root.data in m):
m[root.data] += 1
else:
m[root.data] = 1
# Recursive call for left subtree
traverse(root.left)
# Recursive call for right subtree
traverse(root.right)
# Function to print all the elements of
# two given binary trees in sorted order
def printAllElements(root1, root2):
# Traverse the 1st tree
traverse(root1)
# Traverse the 2nd tree
traverse(root2)
v = []
# Traverse the map
for key in m:
# Print current element
# its frequency times
for i in range(m[key]):
v.append(key)
v.sort()
for i in range(len(v)):
print(v[i], end=" ")
# Driver code
root1 = node(8)
root1.left = node(2)
root1.right = node(10)
root1.left.left = node(1)
root2 = node(5)
root2.left = node(3)
root2.right = node(0)
printAllElements(root1, root2)
# This code is contributed by Saurabh Jaiswal
C#
// C# program of the above approach
using System;
using System.Collections;
using System.Collections.Generic;
public class GFG {
// Structure of a binary tree node
public class Node {
public int data;
public Node left, right;
public Node(int data)
{
left = right = null;
this.data = data;
}
}
// Dictionary to store all elements from given two trees
static Dictionary<int, int> m
= new Dictionary<int, int>();
// Recursive function to perform inorder traversal on
// tree
public static void traverse(Node root)
{
// Base Case
if (root == null)
return;
else {
// Update map
if (m.ContainsKey(root.data))
m[root.data] += 1;
else
m.Add(root.data, 1);
}
// Recursive call for left subtree
traverse(root.left);
// Recursive call for right subtree
traverse(root.right);
}
// Function to print all the elements of two given
// binary trees in sorted order
public static void printAllElements(Node root1,
Node root2)
{
// Traverse the 1st tree
traverse(root1);
// Traverse the 2nd tree
traverse(root2);
ArrayList v = new ArrayList();
// Traverse the map.
foreach(KeyValuePair<int, int> it in m)
{
for (int i = 0; i < it.Value; i++) {
v.Add(it.Key);
}
}
v.Sort();
foreach(var i in v) { Console.Write(i + " "); }
}
static public void Main()
{
// Code
Node root1 = new Node(8);
root1.left = new Node(2);
root1.right = new Node(10);
root1.left.left = new Node(1);
Node root2 = new Node(5);
root2.left = new Node(3);
root2.right = new Node(0);
printAllElements(root1, root2);
}
}
// This code is contributed by lokesh (lokeshmvs21).
Javascript
<script>
// JavaScript code for the above approach
// Structure of a binary tree node
class node {
constructor(d) {
this.data = d;
this.left = null;
this.right = null;
}
};
// Map to store all elements
// from given two trees
let m = new Map();
// Recursive function to perform
// inorder traversal on tree
function traverse(root)
{
// Base Case
if (root == null)
return;
else
{
// Update map
if (m.has(root.data))
{
m.set(root.data, m.get(root.data) + 1);
}
else {
m.set(root.data, 1)
}
}
// Recursive call for left subtree
traverse(root.left);
// Recursive call for right subtree
traverse(root.right);
}
// Function to print all the elements of
// two given binary trees in sorted order
function printAllElements(root1, root2)
{
// Traverse the 1st tree
traverse(root1);
// Traverse the 2nd tree
traverse(root2);
let v = []
// Traverse the map
for (let [key, val] of m)
{
// Print current element
// its frequency times
for (let i = 0; i < val; i++) {
v.push(key);
}
}
v.sort(function (a, b) { return a - b })
for (let i = 0; i < v.length; i++) {
document.write(v[i] + " ")
}
}
// Driver code
let root1 = new node(8);
root1.left = new node(2);
root1.right = new node(10);
root1.left.left = new node(1);
let root2 = new node(5);
root2.left = new node(3);
root2.right = new node(0);
printAllElements(root1, root2);
// This code is contributed by Potta Lokesh
</script>
Producción
0 1 2 3 5 8 10
Complejidad de tiempo : O(N*log N)
Espacio auxiliar : O(N)