Dado un árbol binario perfecto , imprima Nodes de nivel medio sin calcular su altura. Un árbol binario perfecto es un árbol binario en el que todos los Nodes interiores tienen dos hijos y todas las hojas tienen la misma profundidad o el mismo nivel.
C++
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has key, pointer to left
child and a pointer to right child */
struct Node {
int key;
struct Node *left, *right;
};
/* To create a newNode of tree and return pointer */
struct Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Takes two parameters - same initially and
// calls recursively
void printMiddleLevelUtil(Node* a, Node* b)
{
// Base case e
if (a == NULL || b == NULL)
return;
// Fast pointer has reached the leaf so print
// value at slow pointer
if ((b->left == NULL) && (b->right == NULL)) {
cout << a->key << " ";
return;
}
// Recursive call
// root.left.left and root.left.right will
// print same value
// root.right.left and root.right.right
// will print same value
// So we use any one of the condition
if (b->left->left) {
printMiddleLevelUtil(a->left, b->left->left);
printMiddleLevelUtil(a->right, b->left->left);
}
else {
printMiddleLevelUtil(a->left, b->left);
printMiddleLevelUtil(a->right, b->left);
}
}
// Main printing method that take a Tree as input
void printMiddleLevel(Node* node)
{
printMiddleLevelUtil(node, node);
}
// Driver program to test above functions
int main()
{
Node* n1 = newNode(1);
Node* n2 = newNode(2);
Node* n3 = newNode(3);
Node* n4 = newNode(4);
Node* n5 = newNode(5);
Node* n6 = newNode(6);
Node* n7 = newNode(7);
n2->left = n4;
n2->right = n5;
n3->left = n6;
n3->right = n7;
n1->left = n2;
n1->right = n3;
printMiddleLevel(n1);
}
// This code is contributed by Prasad Kshirsagar
Java
// Tree node definition
class Node {
public int key;
public Node left;
public Node right;
public Node(int val)
{
this.left = null;
this.right = null;
this.key = val;
}
}
public class PrintMiddle
{
// Takes two parameters - same initially and
// calls recursively
private static void printMiddleLevelUtil(Node a, Node b)
{
// Base case e
if (a == null || b == null)
return;
// Fast pointer has reached the leaf so print
// value at slow pointer
if ((b.left == null) && (b.right == null))
{
System.out.print(a.key + " ");
return;
}
// Recursive call
// root.left.left and root.left.right will
// print same value
// root.right.left and root.right.right
// will print same value
// So we use any one of the condition
if (b.left.left!=null)
{
printMiddleLevelUtil(a.left, b.left.left);
printMiddleLevelUtil(a.right, b.left.left);
}
else
{
printMiddleLevelUtil(a.left, b.left);
printMiddleLevelUtil(a.right, b.left);
}
}
// Main printing method that take a Tree as input
public static void printMiddleLevel(Node node)
{
printMiddleLevelUtil(node, node);
}
// Driver code
public static void main(String[] args)
{
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
Node n7 = new Node(7);
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
n1.left = n2;
n1.right = n3;
printMiddleLevel(n1);
}
}
Python3
''' A binary tree node has key, pointer to left child and a pointer to right child ''' class Node: def __init__(self, key): self.key=key self.left = None self.right = None # To create a newNode of tree and return pointer def newNode(key): temp = Node(key) return temp # Takes two parameters - same initially and # calls recursively def printMiddleLevelUtil(a, b): # Base case e if (a == None or b == None): return; # Fast pointer has reached the leaf so print # value at slow pointer if ((b.left == None) and (b.right == None)): print(a.key, end=' ') return; # Recursive call # root.left.left and root.left.right will # print same value # root.right.left and root.right.right # will print same value # So we use any one of the condition if (b.left.left): printMiddleLevelUtil(a.left, b.left.left); printMiddleLevelUtil(a.right, b.left.left); else: printMiddleLevelUtil(a.left, b.left); printMiddleLevelUtil(a.right, b.left); # Main printing method that take a Tree as input def printMiddleLevel(node): printMiddleLevelUtil(node, node); # Driver program to test above functions if __name__=='__main__': n1 = newNode(1); n2 = newNode(2); n3 = newNode(3); n4 = newNode(4); n5 = newNode(5); n6 = newNode(6); n7 = newNode(7); n2.left = n4; n2.right = n5; n3.left = n6; n3.right = n7; n1.left = n2; n1.right = n3; printMiddleLevel(n1); # This code is contributed by rutvik_56
C#
using System;
// Tree node definition
public class Node {
public int key;
public Node left;
public Node right;
public Node(int val)
{
this.left = null;
this.right = null;
this.key = val;
}
}
public class PrintMiddle
{
// Takes two parameters - same initially and
// calls recursively
private static void printMiddleLevelUtil(Node a, Node b)
{
// Base case e
if (a == null || b == null)
return;
// Fast pointer has reached the leaf so print
// value at slow pointer
if ((b.left == null) && (b.right == null))
{
Console.Write(a.key + " ");
return;
}
// Recursive call
// root.left.left and root.left.right will
// print same value
// root.right.left and root.right.right
// will print same value
// So we use any one of the condition
if (b.left.left!=null)
{
printMiddleLevelUtil(a.left, b.left.left);
printMiddleLevelUtil(a.right, b.left.left);
}
else
{
printMiddleLevelUtil(a.left, b.left);
printMiddleLevelUtil(a.right, b.left);
}
}
// Main printing method that take a Tree as input
public static void printMiddleLevel(Node node)
{
printMiddleLevelUtil(node, node);
}
// Driver code
public static void Main(String[] args)
{
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
Node n7 = new Node(7);
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
n1.left = n2;
n1.right = n3;
printMiddleLevel(n1);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Tree node definition
class Node
{
constructor(val) {
this.left = null;
this.right = null;
this.key = val;
}
}
// Takes two parameters - same initially and
// calls recursively
function printMiddleLevelUtil(a, b)
{
// Base case e
if (a == null || b == null)
return;
// Fast pointer has reached the leaf so print
// value at slow pointer
if ((b.left == null) && (b.right == null))
{
document.write(a.key + " ");
return;
}
// Recursive call
// root.left.left and root.left.right will
// print same value
// root.right.left and root.right.right
// will print same value
// So we use any one of the condition
if (b.left.left != null)
{
printMiddleLevelUtil(a.left, b.left.left);
printMiddleLevelUtil(a.right, b.left.left);
}
else
{
printMiddleLevelUtil(a.left, b.left);
printMiddleLevelUtil(a.right, b.left);
}
}
// Main printing method that take a Tree as input
function printMiddleLevel(node)
{
printMiddleLevelUtil(node, node);
}
let n1 = new Node(1);
let n2 = new Node(2);
let n3 = new Node(3);
let n4 = new Node(4);
let n5 = new Node(5);
let n6 = new Node(6);
let n7 = new Node(7);
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
n1.left = n2;
n1.right = n3;
printMiddleLevel(n1);
// This code is contributed by suresh07.
</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