El recorrido de hojas es una secuencia de hojas atravesadas de izquierda a derecha. El problema es verificar si los recorridos de las hojas de dos árboles binarios dados son iguales o no.
Complejidad del tiempo esperado O(n). Espacio auxiliar esperado O(h1 + h2) donde h1 y h2 son alturas de dos árboles binarios.
Ejemplos:
C++
// C++ code to check if leaf traversals
// of two Binary Trees are same or not.
#include <bits/stdc++.h>
using namespace std;
// Binary Tree Node
struct Node {
int data;
Node* left;
Node* right;
};
// Returns new Node with data as
// input to below function.
Node* newNode(int d)
{
Node* temp = new Node;
temp->data = d;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// checks if a given node is leaf or not.
bool isLeaf(Node* root)
{
if (root == NULL)
return false;
if (!root->left && !root->right)
return true;
return false;
}
// iterative function.
// returns true if leaf traversals
// are same, else false.
bool isSame(Node* root1, Node* root2)
{
stack<Node*> s1;
stack<Node*> s2;
// push root1 to empty stack s1.
s1.push(root1);
// push root2 to empty stack s2.
s2.push(root2);
// loop until either of stacks are non-empty.
while (!s1.empty() || !s2.empty())
{
// this means one of the stacks has
// extra leaves, hence return false.
if (s1.empty() || s2.empty())
return false;
Node* temp1 = s1.top();
s1.pop();
while (temp1 != NULL && !isLeaf(temp1))
{
// Push right child if exists
if (temp1->right)
s1.push(temp1->right);
// Push left child if exists
if (temp1->left)
s1.push(temp1->left);
// Note that right child(if exists)
// is pushed before left child(if exists).
temp1 = s1.top();
s1.pop();
}
Node* temp2 = s2.top();
s2.pop();
while (temp2 != NULL && !isLeaf(temp2))
{
// Push right child if exists
if (temp2->right)
s2.push(temp2->right);
// Push left child if exists
if (temp2->left)
s2.push(temp2->left);
temp2 = s2.top();
s2.pop();
}
if (!temp1 && temp2)
return false;
if (temp1 && !temp2)
return false;
if (temp1 && temp2) {
return temp1->data == temp2->data;
}
}
// all leaves are matched
return true;
}
// Driver Code
int main()
{
Node* root1 = newNode(1);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(4);
root1->right->left = newNode(6);
root1->right->right = newNode(7);
Node* root2 = newNode(0);
root2->left = newNode(1);
root2->right = newNode(5);
root2->left->right = newNode(4);
root2->right->left = newNode(6);
root2->right->right = newNode(7);
if (isSame(root1, root2))
cout << "Same";
else
cout << "Not Same";
return 0;
}
// This code is contributed
// by AASTHA VARMA
Java
// Java program to check if two Leaf Traversal of
// Two Binary Trees is same or not
import java.util.*;
import java.lang.*;
import java.io.*;
// Binary Tree node
class Node
{
int data;
Node left, right;
public Node(int x)
{
data = x;
left = right = null;
}
public boolean isLeaf()
{
return (left == null && right == null);
}
}
class LeafOrderTraversal
{
// Returns true of leaf traversal of two trees is
// same, else false
public static boolean isSame(Node root1, Node root2)
{
// Create empty stacks. These stacks are going
// to be used for iterative traversals.
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.push(root1);
s2.push(root2);
// Loop until either of two stacks is not empty
while (!s1.empty() || !s2.empty())
{
// If one of the stacks is empty means other
// stack has extra leaves so return false
if (s1.empty() || s2.empty())
return false;
Node temp1 = s1.pop();
while (temp1 != null && !temp1.isLeaf())
{
// Push right and left children of temp1.
// Note that right child is inserted
// before left
if (temp1.right != null)
s1.push(temp1.right);
if (temp1.left != null)
s1.push(temp1.left);
temp1 = s1.pop();
}
// same for tree2
Node temp2 = s2.pop();
while (temp2 != null && !temp2.isLeaf())
{
if (temp2.right != null)
s2.push(temp2.right);
if (temp2.left != null)
s2.push(temp2.left);
temp2 = s2.pop();
}
// If one is null and other is not, then
// return false
if (temp1 == null && temp2 != null)
return false;
if (temp1 != null && temp2 == null)
return false;
// If both are not null and data is not
// same return false
if (temp1 != null && temp2 != null)
{
if (temp1.data != temp2.data)
return false;
}
}
// If control reaches this point, all leaves
// are matched
return true;
}
// Driver code
public static void main(String[] args)
{
// Let us create trees in above example 1
Node root1 = new Node(1);
root1.left = new Node(2);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.right.left = new Node(6);
root1.right.right = new Node(7);
Node root2 = new Node(0);
root2.left = new Node(1);
root2.right = new Node(5);
root2.left.right = new Node(4);
root2.right.left = new Node(6);
root2.right.right = new Node(7);
if (isSame(root1, root2))
System.out.println("Same");
else
System.out.println("Not Same");
}
}
Python3
# Python3 program to check if two Leaf
# Traversal of Two Binary Trees is same or not
# Binary Tree node
class Node:
def __init__(self, x):
self.data = x
self.left = self.right = None
def isLeaf(self):
return (self.left == None and
self.right == None)
# Returns true of leaf traversal of
# two trees is same, else false
def isSame(root1, root2):
# Create empty stacks. These stacks are going
# to be used for iterative traversals.
s1 = []
s2 = []
s1.append(root1)
s2.append(root2)
# Loop until either of two stacks
# is not empty
while (len(s1) != 0 or len(s2) != 0):
# If one of the stacks is empty means other
# stack has extra leaves so return false
if (len(s1) == 0 or len(s2) == 0):
return False
temp1 = s1.pop(-1)
while (temp1 != None and not temp1.isLeaf()):
# append right and left children of temp1.
# Note that right child is inserted
# before left
if (temp1.right != None):
s1.append(temp1. right)
if (temp1.left != None):
s1.append(temp1.left)
temp1 = s1.pop(-1)
# same for tree2
temp2 = s2.pop(-1)
while (temp2 != None and not temp2.isLeaf()):
if (temp2.right != None):
s2.append(temp2.right)
if (temp2.left != None):
s2.append(temp2.left)
temp2 = s2.pop(-1)
# If one is None and other is not,
# then return false
if (temp1 == None and temp2 != None):
return False
if (temp1 != None and temp2 == None):
return False
# If both are not None and data is
# not same return false
if (temp1 != None and temp2 != None):
if (temp1.data != temp2.data):
return False
# If control reaches this point,
# all leaves are matched
return True
# Driver Code
if __name__ == '__main__':
# Let us create trees in above example 1
root1 = Node(1)
root1.left = Node(2)
root1.right = Node(3)
root1.left.left = Node(4)
root1.right.left = Node(6)
root1.right.right = Node(7)
root2 = Node(0)
root2.left = Node(1)
root2.right = Node(5)
root2.left.right = Node(4)
root2.right.left = Node(6)
root2.right.right = Node(7)
if (isSame(root1, root2)):
print("Same")
else:
print("Not Same")
# This code is contributed by pranchalK
C#
// C# program to check if two Leaf Traversal
// of Two Binary Trees is same or not
using System;
using System.Collections.Generic;
// Binary Tree node
public class Node {
public int data;
public Node left, right;
public Node(int x)
{
data = x;
left = right = null;
}
public virtual bool Leaf
{
get {
return (left == null && right == null);
}
}
}
class GFG {
// Returns true of leaf traversal of
// two trees is same, else false
public static bool isSame(Node root1, Node root2)
{
// Create empty stacks. These stacks
// are going to be used for iterative
// traversals.
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.Push(root1);
s2.Push(root2);
// Loop until either of two stacks
// is not empty
while (s1.Count > 0 || s2.Count > 0)
{
// If one of the stacks is empty means other
// stack has extra leaves so return false
if (s1.Count == 0 || s2.Count == 0)
{
return false;
}
Node temp1 = s1.Pop();
while (temp1 != null && !temp1.Leaf)
{
// Push right and left children of temp1.
// Note that right child is inserted
// before left
if (temp1.right != null)
{
s1.Push(temp1.right);
}
if (temp1.left != null)
{
s1.Push(temp1.left);
}
temp1 = s1.Pop();
}
// same for tree2
Node temp2 = s2.Pop();
while (temp2 != null && !temp2.Leaf)
{
if (temp2.right != null)
{
s2.Push(temp2.right);
}
if (temp2.left != null)
{
s2.Push(temp2.left);
}
temp2 = s2.Pop();
}
// If one is null and other is not,
// then return false
if (temp1 == null && temp2 != null)
{
return false;
}
if (temp1 != null && temp2 == null)
{
return false;
}
// If both are not null and data
// is not same return false
if (temp1 != null && temp2 != null)
{
if (temp1.data != temp2.data)
{
return false;
}
}
}
// If control reaches this point,
// all leaves are matched
return true;
}
// Driver Code
public static void Main(string[] args)
{
// Let us create trees in above example 1
Node root1 = new Node(1);
root1.left = new Node(2);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.right.left = new Node(6);
root1.right.right = new Node(7);
Node root2 = new Node(0);
root2.left = new Node(1);
root2.right = new Node(5);
root2.left.right = new Node(4);
root2.right.left = new Node(6);
root2.right.right = new Node(7);
if (isSame(root1, root2)) {
Console.WriteLine("Same");
}
else {
Console.WriteLine("Not Same");
}
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// JavaScript program to check if two Leaf Traversal of
// Two Binary Trees is same or not
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Returns true of leaf traversal of two trees is
// same, else false
function isSame(root1, root2)
{
// Create empty stacks. These stacks are going
// to be used for iterative traversals.
let s1 = [];
let s2 = [];
s1.push(root1);
s2.push(root2);
// Loop until either of two stacks is not empty
while (s1.length > 0 || s2.length > 0)
{
// If one of the stacks is empty means other
// stack has extra leaves so return false
if (s1.length == 0 || s1.length == 0)
return false;
let temp1 = s1.pop();
while (temp1 != null && !(temp1.left == null &&
temp1.right == null))
{
// Push right and left children of temp1.
// Note that right child is inserted
// before left
if (temp1.right != null)
s1.push(temp1.right);
if (temp1.left != null)
s1.push(temp1.left);
temp1 = s1.pop();
}
// same for tree2
let temp2 = s2.pop();
while (temp2 != null && !(temp2.left == null &&
temp2.right == null))
{
if (temp2.right != null)
s2.push(temp2.right);
if (temp2.left != null)
s2.push(temp2.left);
temp2 = s2.pop();
}
// If one is null and other is not, then
// return false
if (temp1 == null && temp2 != null)
return false;
if (temp1 != null && temp2 == null)
return false;
// If both are not null and data is not
// same return false
if (temp1 != null && temp2 != null)
{
if (temp1.data != temp2.data)
return false;
}
}
// If control reaches this point, all leaves
// are matched
return true;
}
// Let us create trees in above example 1
let root1 = new Node(1);
root1.left = new Node(2);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.right.left = new Node(6);
root1.right.right = new Node(7);
let root2 = new Node(0);
root2.left = new Node(1);
root2.right = new Node(5);
root2.left.right = new Node(4);
root2.right.left = new Node(6);
root2.right.right = new Node(7);
if (isSame(root1, root2))
document.write("Same");
else
document.write("Not Same");
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA