Dada una raíz de un árbol y un número entero k. Imprime todos los Nodes que están a k distancia de la raíz.
Ejemplo :
C++
// CPP program to print all nodes of level k
// iterative approach
/* binary tree
root is at level 1
20
/ \
10 30
/ \ / \
5 15 25 40
/
12 */
#include <bits/stdc++.h>
using namespace std;
// Node of binary tree
struct Node {
int data;
Node* left, * right;
};
// Function to add a new node
Node* newNode(int data)
{
Node* newnode = new Node();
newnode->data = data;
newnode->left = newnode->right = NULL;
}
// Function to print nodes of given level
bool printKDistant(Node* root, int klevel)
{
queue<Node*> q;
int level = 1;
bool flag = false;
q.push(root);
// extra NULL is pushed to keep track
// of all the nodes to be pushed before
// level is incremented by 1
q.push(NULL);
while (!q.empty()) {
Node* temp = q.front();
// print when level is equal to k
if (level == klevel && temp != NULL) {
flag = true;
cout << temp->data << " ";
}
q.pop();
if (temp == NULL) {
if (q.front())
q.push(NULL);
level += 1;
// break the loop if level exceeds
// the given level number
if (level > klevel)
break;
} else {
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
}
cout << endl;
return flag;
}
// Driver code
int main()
{
// create a binary tree
Node* root = newNode(20);
root->left = newNode(10);
root->right = newNode(30);
root->left->left = newNode(5);
root->left->right = newNode(15);
root->left->right->left = newNode(12);
root->right->left = newNode(25);
root->right->right = newNode(40);
cout << "data at level 1 : ";
int ret = printKDistant(root, 1);
if (ret == false)
cout << "Number exceeds total number of levels\n";
cout << "data at level 2 : ";
ret = printKDistant(root, 2);
if (ret == false)
cout << "Number exceeds total number of levels\n";
cout << "data at level 3 : ";
ret = printKDistant(root, 3);
if (ret == false)
cout << "Number exceeds total number of levels\n";
cout << "data at level 6 : ";
ret = printKDistant(root, 6);
if (ret == false)
cout << "Number exceeds total number of levels\n";
return 0;
}
Java
// Java program to print all nodes of level k
// iterative approach
/* binary tree
root is at level 1
20
/ \
10 30
/ \ / \
5 15 25 40
/
12 */
import java.util.*;
class GFG
{
// Node of binary tree
static class Node
{
int data;
Node left, right;
}
// Function to add a new node
static Node newNode(int data)
{
Node newnode = new Node();
newnode.data = data;
newnode.left = newnode.right = null;
return newnode;
}
// Function to print nodes of given level
static boolean printKDistant(Node root, int klevel)
{
Queue<Node> q = new LinkedList<>();
int level = 1;
boolean flag = false;
q.add(root);
// extra null is added to keep track
// of all the nodes to be added before
// level is incremented by 1
q.add(null);
while (q.size() > 0)
{
Node temp = q.peek();
// print when level is equal to k
if (level == klevel && temp != null)
{
flag = true;
System.out.print( temp.data + " ");
}
q.remove();
if (temp == null)
{
if (q.peek() != null)
q.add(null);
level += 1;
// break the loop if level exceeds
// the given level number
if (level > klevel)
break;
}
else
{
if (temp.left != null)
q.add(temp.left);
if (temp.right != null)
q.add(temp.right);
}
}
System.out.println();
return flag;
}
// Driver code
public static void main(String srga[])
{
// create a binary tree
Node root = newNode(20);
root.left = newNode(10);
root.right = newNode(30);
root.left.left = newNode(5);
root.left.right = newNode(15);
root.left.right.left = newNode(12);
root.right.left = newNode(25);
root.right.right = newNode(40);
System.out.print( "data at level 1 : ");
boolean ret = printKDistant(root, 1);
if (ret == false)
System.out.print( "Number exceeds total " +
"number of levels\n");
System.out.print("data at level 2 : ");
ret = printKDistant(root, 2);
if (ret == false)
System.out.print("Number exceeds total " +
"number of levels\n");
System.out.print( "data at level 3 : ");
ret = printKDistant(root, 3);
if (ret == false)
System.out.print("Number exceeds total " +
"number of levels\n");
System.out.print( "data at level 6 : ");
ret = printKDistant(root, 6);
if (ret == false)
System.out.print( "Number exceeds total" +
"number of levels\n");
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to print all nodes of level k
# iterative approach
""" binary tree
root is at level 1
20
/ \
10 30
/ \ / \
5 15 25 40
/
12 """
# Node of binary tree
# Function to add a new node
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# Function to print nodes of given level
def printKDistant( root, klevel):
q = []
level = 1
flag = False
q.append(root)
# extra None is appended to keep track
# of all the nodes to be appended
# before level is incremented by 1
q.append(None)
while (len(q)):
temp = q[0]
# print when level is equal to k
if (level == klevel and temp != None):
flag = True
print(temp.data, end = " ")
q.pop(0)
if (temp == None) :
if (len(q)):
q.append(None)
level += 1
# break the loop if level exceeds
# the given level number
if (level > klevel) :
break
else:
if (temp.left) :
q.append(temp.left)
if (temp.right) :
q.append(temp.right)
print()
return flag
# Driver Code
if __name__ == '__main__':
root = newNode(20)
root.left = newNode(10)
root.right = newNode(30)
root.left.left = newNode(5)
root.left.right = newNode(15)
root.left.right.left = newNode(12)
root.right.left = newNode(25)
root.right.right = newNode(40)
print("data at level 1 : ", end = "")
ret = printKDistant(root, 1)
if (ret == False):
print("Number exceeds total",
"number of levels")
print("data at level 2 : ", end = "")
ret = printKDistant(root, 2)
if (ret == False) :
print("Number exceeds total",
"number of levels")
print("data at level 3 : ", end = "")
ret = printKDistant(root, 3)
if (ret == False) :
print("Number exceeds total",
"number of levels")
print("data at level 6 : ", end = "")
ret = printKDistant(root, 6)
if (ret == False):
print("Number exceeds total number of levels")
# This code is contributed
# by SHUBHAMSINGH10
C#
// C# program to print all nodes of level k
// iterative approach
/* binary tree
root is at level 1
20
/ \
10 30
/ \ / \
5 15 25 40
/
12 */
using System;
using System.Collections.Generic;
class GFG
{
// Node of binary tree
public class Node
{
public int data;
public Node left, right;
}
// Function to add a new node
static Node newNode(int data)
{
Node newnode = new Node();
newnode.data = data;
newnode.left = newnode.right = null;
return newnode;
}
// Function to print nodes of given level
static Boolean printKDistant(Node root, int klevel)
{
Queue<Node> q = new Queue<Node>();
int level = 1;
Boolean flag = false;
q.Enqueue(root);
// extra null is added to keep track
// of all the nodes to be added before
// level is incremented by 1
q.Enqueue(null);
while (q.Count > 0)
{
Node temp = q.Peek();
// print when level is equal to k
if (level == klevel && temp != null)
{
flag = true;
Console.Write( temp.data + " ");
}
q.Dequeue();
if (temp == null)
{
if (q.Count > 0&&q.Peek() != null)
q.Enqueue(null);
level += 1;
// break the loop if level exceeds
// the given level number
if (level > klevel)
break;
}
else
{
if (temp.left != null)
q.Enqueue(temp.left);
if (temp.right != null)
q.Enqueue(temp.right);
}
}
Console.Write("\n");
return flag;
}
// Driver code
public static void Main(String []srga)
{
// create a binary tree
Node root = newNode(20);
root.left = newNode(10);
root.right = newNode(30);
root.left.left = newNode(5);
root.left.right = newNode(15);
root.left.right.left = newNode(12);
root.right.left = newNode(25);
root.right.right = newNode(40);
Console.Write( "data at level 1 : ");
Boolean ret = printKDistant(root, 1);
if (ret == false)
Console.Write( "Number exceeds total " +
"number of levels\n");
Console.Write("data at level 2 : ");
ret = printKDistant(root, 2);
if (ret == false)
Console.Write("Number exceeds total " +
"number of levels\n");
Console.Write( "data at level 3 : ");
ret = printKDistant(root, 3);
if (ret == false)
Console.Write("Number exceeds total " +
"number of levels\n");
Console.Write( "data at level 6 : ");
ret = printKDistant(root, 6);
if (ret == false)
Console.Write( "Number exceeds total" +
"number of levels\n");
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to print all nodes of level k
// iterative approach
/* binary tree
root is at level 1
20
/ \
10 30
/ \ / \
5 15 25 40
/
12 */
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Function to add a new node
function newNode(data)
{
let newnode = new Node(data);
return newnode;
}
// Function to print nodes of given level
function printKDistant(root, klevel)
{
let q = [];
let level = 1;
let flag = false;
q.push(root);
// extra null is added to keep track
// of all the nodes to be added before
// level is incremented by 1
q.push(null);
while (q.length > 0)
{
let temp = q[0];
// print when level is equal to k
if (level == klevel && temp != null)
{
flag = true;
document.write( temp.data + " ");
}
q.shift();
if (temp == null)
{
if (q[0] != null)
q.push(null);
level += 1;
// break the loop if level exceeds
// the given level number
if (level > klevel)
break;
}
else
{
if (temp.left != null)
q.push(temp.left);
if (temp.right != null)
q.push(temp.right);
}
}
document.write("</br>");
return flag;
}
// create a binary tree
let root = newNode(20);
root.left = newNode(10);
root.right = newNode(30);
root.left.left = newNode(5);
root.left.right = newNode(15);
root.left.right.left = newNode(12);
root.right.left = newNode(25);
root.right.right = newNode(40);
document.write( "data at level 1 : ");
let ret = printKDistant(root, 1);
if (ret == false)
document.write( "Number exceeds total " +
"number of levels" + "</br>");
document.write("data at level 2 : ");
ret = printKDistant(root, 2);
if (ret == false)
document.write("Number exceeds total " +
"number of levels" + "</br>");
document.write( "data at level 3 : ");
ret = printKDistant(root, 3);
if (ret == false)
document.write("Number exceeds total " +
"number of levels" + "</br>");
document.write( "data at level 6 : ");
ret = printKDistant(root, 6);
if (ret == false)
document.write( "Number exceeds total" +
"number of levels" + "</br>");
// 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