Dados dos árboles binarios , la tarea es crear un árbol binario máximo a partir de los dos árboles binarios dados e imprimir el recorrido en orden de ese árbol.
¿Cuál es el árbol binario máximo?
El binario máximo se construye de la siguiente manera:
en el caso de que ambos árboles binarios tengan dos Nodes correspondientes, el máximo de los dos valores se considera como el valor de Node del árbol binario máximo.
Si alguno de los dos Nodes es NULL y si el otro Node no es nulo, inserte ese valor en ese Node del árbol binario máximo.
Ejemplo:
Input:
Tree 1 Tree 2
3 5
/ \ / \
2 6 1 8
/ \ \
20 2 8
Output: 20 2 2 5 8 8
Explanation:
5
/ \
2 8
/ \ \
20 2 8
To construct the required Binary Tree,
Root Node value: Max(3, 5) = 5
Root->left value: Max(2, 1) = 2
Root->right value: Max(6, 8) = 8
Root->left->left value: 20
Root->left->right value: 2
Root->right->right value: 8
Input:
Tree 1 Tree 2
9 5
/ \ / \
2 6 1 8
/ \ \ \
20 3 2 8
Output: 20 2 3 9 8 8
Explanation:
9
/ \
2 8
/ \ \
20 3 8
Enfoque:
siga los pasos que se indican a continuación para resolver el problema:
- Atraviese ambos árboles utilizando el recorrido de preorden .
- Si ambos Nodes son NULL , regresa. De lo contrario, verifique las siguientes condiciones:
- Si ambos Nodes no son NULL , almacene el máximo entre ellos como el valor del Node del árbol binario máximo .
- Si solo uno de los Nodes es NULL , almacene el valor del Node no NULL como el valor del Node del árbol binario máximo .
- Atraviesa recursivamente los subárboles izquierdos.
- Atraviesa recursivamente los subárboles correctos
- Finalmente, devuelva la raíz del árbol binario máximo .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the Maximum
// Binary Tree from two Binary Trees
#include<bits/stdc++.h>
using namespace std;
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
class Node{
public:
int data;
Node *left, *right;
Node(int data, Node *left,
Node *right)
{
this->data = data;
this->left = left;
this->right = right;
}
};
// Helper method that allocates
// a new node with the given data
// and NULL left and right pointers.
Node* newNode(int data)
{
Node *tmp = new Node(data, NULL, NULL);
return tmp;
}
// Given a binary tree, print
// its nodes in inorder
void inorder(Node *node)
{
if (node == NULL)
return;
// First recur on left child
inorder(node->left);
// Then print the data of node
cout << node->data << " ";
// Now recur on right child
inorder(node->right);
}
// Method to find the maximum
// binary tree from two binary trees
Node* MaximumBinaryTree(Node *t1, Node *t2)
{
if (t1 == NULL)
return t2;
if (t2 == NULL)
return t1;
t1->data = max(t1->data, t2->data);
t1->left = MaximumBinaryTree(t1->left,
t2->left);
t1->right = MaximumBinaryTree(t1->right,
t2->right);
return t1;
}
// Driver Code
int main()
{
/* First Binary Tree
3
/ \
2 6
/
20
*/
Node *root1 = newNode(3);
root1->left = newNode(2);
root1->right = newNode(6);
root1->left->left = newNode(20);
/* Second Binary Tree
5
/ \
1 8
\ \
2 8
*/
Node *root2 = newNode(5);
root2->left = newNode(1);
root2->right = newNode(8);
root2->left->right = newNode(2);
root2->right->right = newNode(8);
Node *root3 = MaximumBinaryTree(root1, root2);
inorder(root3);
}
// This code is contributed by pratham76
Java
// Java program to find the Maximum
// Binary Tree from two Binary Trees
/* A binary tree node has data,
pointer to left child
and a pointer to right child */
class Node {
int data;
Node left, right;
public Node(int data, Node left,
Node right)
{
this.data = data;
this.left = left;
this.right = right;
}
/* Helper method that allocates
a new node with the given data
and NULL left and right pointers. */
static Node newNode(int data)
{
return new Node(data, null, null);
}
/* Given a binary tree, print
its nodes in inorder*/
static void inorder(Node node)
{
if (node == null)
return;
/* first recur on left child */
inorder(node.left);
/* then print the data of node */
System.out.printf("%d ", node.data);
/* now recur on right child */
inorder(node.right);
}
/* Method to find the maximum
binary tree from
two binary trees*/
static Node MaximumBinaryTree(Node t1, Node t2)
{
if (t1 == null)
return t2;
if (t2 == null)
return t1;
t1.data = Math.max(t1.data, t2.data);
t1.left = MaximumBinaryTree(t1.left,
t2.left);
t1.right = MaximumBinaryTree(t1.right,
t2.right);
return t1;
}
// Driver Code
public static void main(String[] args)
{
/* First Binary Tree
3
/ \
2 6
/
20
*/
Node root1 = newNode(3);
root1.left = newNode(2);
root1.right = newNode(6);
root1.left.left = newNode(20);
/* Second Binary Tree
5
/ \
1 8
\ \
2 8
*/
Node root2 = newNode(5);
root2.left = newNode(1);
root2.right = newNode(8);
root2.left.right = newNode(2);
root2.right.right = newNode(8);
Node root3
= MaximumBinaryTree(root1, root2);
inorder(root3);
}
}
Python3
# Python3 program to find the Maximum # Binary Tree from two Binary Trees ''' A binary tree node has data, pointer to left child and a pointer to right child ''' class Node: def __init__(self, data, left, right): self.data = data self.left = left self.right = right ''' Helper method that allocates a new node with the given data and None left and right pointers. ''' def newNode(data): return Node(data, None, None); ''' Given a binary tree, print its nodes in inorder''' def inorder(node): if (node == None): return; ''' first recur on left child ''' inorder(node.left); ''' then print the data of node ''' print(node.data, end=' '); ''' now recur on right child ''' inorder(node.right); ''' Method to find the maximum binary tree from two binary trees''' def MaximumBinaryTree(t1, t2): if (t1 == None): return t2; if (t2 == None): return t1; t1.data = max(t1.data, t2.data); t1.left = MaximumBinaryTree(t1.left, t2.left); t1.right = MaximumBinaryTree(t1.right, t2.right); return t1; # Driver Code if __name__=='__main__': ''' First Binary Tree 3 / \ 2 6 / 20 ''' root1 = newNode(3); root1.left = newNode(2); root1.right = newNode(6); root1.left.left = newNode(20); ''' Second Binary Tree 5 / \ 1 8 \ \ 2 8 ''' root2 = newNode(5); root2.left = newNode(1); root2.right = newNode(8); root2.left.right = newNode(2); root2.right.right = newNode(8); root3 = MaximumBinaryTree(root1, root2); inorder(root3); # This code is contributed by rutvik_56
C#
// C# program to find the Maximum
// Binary Tree from two Binary Trees
using System;
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
class Node{
public int data;
public Node left, right;
public Node(int data, Node left,
Node right)
{
this.data = data;
this.left = left;
this.right = right;
}
// Helper method that allocates
// a new node with the given data
// and NULL left and right pointers.
static Node newNode(int data)
{
return new Node(data, null, null);
}
// Given a binary tree, print
// its nodes in inorder
static void inorder(Node node)
{
if (node == null)
return;
// first recur on left child
inorder(node.left);
// then print the data of node
Console.Write("{0} ", node.data);
// now recur on right child
inorder(node.right);
}
// Method to find the maximum
// binary tree from
// two binary trees
static Node MaximumBinaryTree(Node t1, Node t2)
{
if (t1 == null)
return t2;
if (t2 == null)
return t1;
t1.data = Math.Max(t1.data, t2.data);
t1.left = MaximumBinaryTree(t1.left,
t2.left);
t1.right = MaximumBinaryTree(t1.right,
t2.right);
return t1;
}
// Driver Code
public static void Main(String[] args)
{
/* First Binary Tree
3
/ \
2 6
/
20
*/
Node root1 = newNode(3);
root1.left = newNode(2);
root1.right = newNode(6);
root1.left.left = newNode(20);
/* Second Binary Tree
5
/ \
1 8
\ \
2 8
*/
Node root2 = newNode(5);
root2.left = newNode(1);
root2.right = newNode(8);
root2.left.right = newNode(2);
root2.right.right = newNode(8);
Node root3 = MaximumBinaryTree(root1, root2);
inorder(root3);
}
}
// This code is contributed by Amal Kumar Choubey
Javascript
<script>
// Javascript program to find the Maximum
// Binary Tree from two Binary Trees
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
class Node{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Helper method that allocates
// a new node with the given data
// and NULL left and right pointers.
function newNode(data)
{
return new Node(data, null, null);
}
// Given a binary tree, print
// its nodes in inorder
function inorder(node)
{
if (node == null)
return;
// first recur on left child
inorder(node.left);
// then print the data of node
document.write(node.data + " ");
// now recur on right child
inorder(node.right);
}
// Method to find the maximum
// binary tree from
// two binary trees
function MaximumBinaryTree(t1, t2)
{
if (t1 == null)
return t2;
if (t2 == null)
return t1;
t1.data = Math.max(t1.data, t2.data);
t1.left = MaximumBinaryTree(t1.left,
t2.left);
t1.right = MaximumBinaryTree(t1.right,
t2.right);
return t1;
}
// Driver Code
/* First Binary Tree
3
/ \
2 6
/
20
*/
var root1 = newNode(3);
root1.left = newNode(2);
root1.right = newNode(6);
root1.left.left = newNode(20);
/* Second Binary Tree
5
/ \
1 8
\ \
2 8
*/
var root2 = newNode(5);
root2.left = newNode(1);
root2.right = newNode(8);
root2.left.right = newNode(2);
root2.right.right = newNode(8);
var root3 = MaximumBinaryTree(root1, root2);
inorder(root3);
</script>
Producción:
20 2 2 5 8 8
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Ganeshchowdharysadanala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA