Dado un árbol binario y un entero K, la tarea es imprimir todos los enteros en el nivel K del árbol de izquierda a derecha.
Ejemplos:
Entrada: Árbol en la imagen de abajo, K = 3
Salida : 4 5 6
Explicación: Todos los Nodes presentes en el nivel 3 del árbol binario anterior de izquierda a derecha son 4, 5 y 6.Entrada: Árbol en la imagen de abajo, K = 2
Salida: 9 6
Enfoque: el problema dado se puede resolver con la ayuda de la recursividad utilizando un recorrido DFS . Cree una función recursiva para recorrer el árbol dado y mantener el nivel actual del Node en una variable. Invoque recursivamente el subárbol izquierdo y el subárbol derecho e incremente el nivel en 1 . Si el nivel del Node actual es igual a K , imprime su valor.
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;
// A Binary Tree Node
struct Node {
int data;
struct Node *left, *right;
};
// Recursive function to print all
// nodes of a Binary Tree at a
// given level using DFS traversal
void printNodes(Node* root, int level, int K)
{
// Base Case
if (root == NULL) {
return;
}
// Recursive Call for
// the left subtree
printNodes(root->left, level + 1, K);
// Recursive Call for
// the right subtree
printNodes(root->right, level + 1, K);
// If current level is
// the required level
if (K == level) {
cout << root->data << " ";
}
}
// Function to create a new tree node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver Code
int main()
{
Node* root = newNode(3);
root->left = newNode(9);
root->right = newNode(6);
root->left->left = newNode(11);
int K = 2;
printNodes(root, 1, K);
return 0;
}
Java
// Java Program of the above approach
import java.util.*;
class GFG{
// A Binary Tree Node
static class Node {
int data;
Node left, right;
};
// Recursive function to print all
// nodes of a Binary Tree at a
// given level using DFS traversal
static void printNodes(Node root, int level, int K)
{
// Base Case
if (root == null) {
return;
}
// Recursive Call for
// the left subtree
printNodes(root.left, level + 1, K);
// Recursive Call for
// the right subtree
printNodes(root.right, level + 1, K);
// If current level is
// the required level
if (K == level) {
System.out.print(root.data+ " ");
}
}
// Function to create a new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver Code
public static void main(String[] args)
{
Node root = newNode(3);
root.left = newNode(9);
root.right = newNode(6);
root.left.left = newNode(11);
int K = 2;
printNodes(root, 1, K);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python code for the above approach class Node: def __init__(self, d): self.data = d self.left = None self.right = None # Recursive function to print all # nodes of a Binary Tree at a # given level using DFS traversal def printNodes(root, level, K): # Base Case if (root == None): return # Recursive Call for # the left subtree printNodes(root.left, level + 1, K) # Recursive Call for # the right subtree printNodes(root.right, level + 1, K) # If current level is # the required level if (K == level): print(root.data, end=" ") # Driver Code root = Node(3) root.left = Node(9) root.right = Node(6) root.left.left = Node(11) K = 2 printNodes(root, 1, K) # This code is contributed by gfgking
C#
// C# Program of the above approach
using System;
using System.Collections.Generic;
public class GFG {
// A Binary Tree Node
public class Node {
public int data;
public Node left, right;
};
// Recursive function to print all
// nodes of a Binary Tree at a
// given level using DFS traversal
static void printNodes(Node root, int level, int K) {
// Base Case
if (root == null) {
return;
}
// Recursive Call for
// the left subtree
printNodes(root.left, level + 1, K);
// Recursive Call for
// the right subtree
printNodes(root.right, level + 1, K);
// If current level is
// the required level
if (K == level) {
Console.Write(root.data + " ");
}
}
// Function to create a new tree node
static Node newNode(int data) {
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver Code
public static void Main(String[] args)
{
Node root = newNode(3);
root.left = newNode(9);
root.right = newNode(6);
root.left.left = newNode(11);
int K = 2;
printNodes(root, 1, K);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript code for the above approach
class Node {
constructor(d) {
this.data = d;
this.left = null;
this.right = null;
}
}
// Recursive function to print all
// nodes of a Binary Tree at a
// given level using DFS traversal
function printNodes(root, level, K)
{
// Base Case
if (root == null) {
return;
}
// Recursive Call for
// the left subtree
printNodes(root.left, level + 1, K);
// Recursive Call for
// the right subtree
printNodes(root.right, level + 1, K);
// If current level is
// the required level
if (K == level) {
document.write(root.data + " ");
}
}
// Driver Code
let root = new Node(3);
root.left = new Node(9);
root.right = new Node(6);
root.left.left = new Node(11);
let K = 2;
printNodes(root, 1, K);
// This code is contributed by Potta Lokesh
</script>
Producción
9 6
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)