Dado un árbol binario , la tarea es imprimir todas las rutas de la raíz a la hoja de este árbol en el recorrido de la ruta Boundary Root to Leaf.
Recorrido de ruta de raíz a hoja límite: en este recorrido, la primera ruta de raíz a hoja (límite izquierdo) se imprime primero, seguida por la última ruta de raíz a hoja (límite derecho) en orden inverso. Luego, el proceso se repite para la segunda y penúltima ruta de raíz a hoja, hasta que se haya impreso toda la ruta de raíz a hoja.
Ejemplos:
Input:
1
/ \
15 13
/ / \
11 7 29
\ /
2 3
Output: 1 15 11
3 29 13 1
1 13 7 2
Explanation:
First of all print first path from Root to the Leaf
which is 1 15 11
Then, print the last path from the Leaf to Root
which is 3 29 13 1
Then, print the second path from Root to Leaf
which is 1 13 7 2
Input:
7
/ \
23 41
/ \ \
31 16 3
/ \ \ /
2 5 17 11
/
23
Output: 7 23 31 2
11 3 41 7
7 23 31 5
23 17 16 23 7
Enfoque: Para imprimir caminos en Raíz de límite a Trazado transversal de hoja,
- Primero tenemos que hacer Preorder Traversal del árbol binario para obtener todos los valores de Node de una ruta en particular.
- Aquí se usa una array para almacenar la ruta del árbol mientras se realiza el recorrido Preorder y luego se almacena esta ruta en la array.
- Luego, para cada ruta, imprima la array en la primera fila ( de izquierda a derecha ), luego en la última fila ( de derecha a izquierda ), y así sucesivamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to print the
// path in Boundary Root to Leaf
// Path Traversal.
#include <bits/stdc++.h>
using namespace std;
// Structure of tree node
struct Node {
int key;
struct Node *left, *right;
};
// Utility function to
// create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Function to calculate the length
// of longest path of the tree
int lengthOfLongestPath(struct Node* node)
{
// Base Case
if (node == NULL)
return 0;
// Recursive call to calculate the length
// of longest path
int left = lengthOfLongestPath(node->left);
int right = lengthOfLongestPath(node->right);
return 1 + (left > right ? left : right);
}
// Function to copy the complete
// path in a matrix
void copyPath(int* path, int index,
int** mtrx, int row)
{
// Loop to copy the path
for (int i = 0; i < index; i++) {
mtrx[row][i] = path[i];
}
}
// Function to store all path
// one by one in matrix
void storePath(struct Node* node,
int* path, int index,
int** mtrx, int& row)
{
// Base condition
if (node == NULL) {
return;
}
// Inserting the current node
// into the current path
path[index] = node->key;
// Recursive call for
// the left sub tree
storePath(node->left, path,
index + 1, mtrx, row);
// Recursive call for
// the right sub tree
storePath(node->right, path,
index + 1, mtrx, row);
// Condition to check that current
// node is a leaf node or not
if (node->left == NULL
&& node->right == NULL) {
// Incrementation for changing
// row
row = row + 1;
// Function call for copying
// the path
copyPath(path, index + 1,
mtrx, row);
}
}
// Function to calculate
// total path
int totalPath(Node* node)
{
static int count = 0;
if (node == NULL) {
return count;
}
if (node->left == NULL
&& node->right == NULL) {
return count + 1;
}
count = totalPath(node->left);
return totalPath(node->right);
}
// Function for Clockwise Spiral Traversal
// of Binary Tree
void traverse_matrix(int** mtrx,
int height,
int width)
{
int j = 0, k1 = 0, k2 = 0;
int k3 = height - 1;
int k4 = width - 1;
for (int round = 0; round < height/2; round++)
{
for (j = k2; j < width; j++) {
// Only print those values which
// are not MAX_INTEGER
if (mtrx[k1][j] != INT_MAX) {
cout << mtrx[k1][j] << " ";
}
}
cout << endl;
k2 = 0;
k1++;
for (j = k4; j >= 0; j--) {
// Only print those values which
// are not MAX_INTEGER
if (mtrx[k3][j] != INT_MAX) {
cout << mtrx[k3][j] << " ";
}
}
cout << endl;
k4 = width - 1;
k3--;
}
// Condition (one row may be left
// traversing)
// If number of rows in matrix are odd
if (height % 2 != 0) {
for (j = k2; j < width; j++) {
// Only print those values which are
// not MAX_INTEGER
if (mtrx[k1][j] != INT_MAX) {
cout << mtrx[k1][j] << " ";
}
}
}
}
// Function to print all the paths
// in Boundary Root to Leaf
// Path Traversal
void PrintPath(Node* node)
{
// Calculate the length of
// longest path of the tree
int max_len = lengthOfLongestPath(node);
// Calculate total path
int total_path = totalPath(node);
// Array to store path
int* path = new int[max_len];
memset(path, 0, sizeof(path));
// Use double pointer to create
// 2D array which will contain
// all path of the tree
int** mtrx = new int*[total_path];
// Initialize width for each row
// of matrix
for (int i = 0; i < total_path; i++)
{
mtrx[i] = new int[max_len];
}
// Initialize complete matrix with
// MAX INTEGER(purpose garbage)
for (int i = 0; i < total_path; i++)
{
for (int j = 0; j < max_len; j++)
{
mtrx[i][j] = INT_MAX;
}
}
int row = -1;
storePath(node, path, 0, mtrx, row);
// Print the circular clockwise spiral
// traversal of the tree
traverse_matrix(mtrx, total_path,
max_len);
// Release extra memory
// allocated for matrix
free(mtrx);
}
// Driver Code
int main()
{
/* 10
/ \
13 11
/ \
19 23
/ \ / \
21 29 43 15
/
7 */
// Create Binary Tree as shown
Node* root = newNode(10);
root->left = newNode(13);
root->right = newNode(11);
root->right->left = newNode(19);
root->right->right = newNode(23);
root->right->left->left = newNode(21);
root->right->left->right = newNode(29);
root->right->right->left = newNode(43);
root->right->right->right = newNode(15);
root->right->right->right->left = newNode(7);
// Function Call
PrintPath(root);
return 0;
}
Java
// Java implementation to print the
// path in Boundary Root to Leaf
// Path Traversal.
import java.util.*;
class GFG{
static int row;
static int count = 0;
// Structure of tree node
static class Node
{
int key;
Node left, right;
};
// Utility function to
// create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Function to calculate the length
// of longest path of the tree
static int lengthOfLongestPath(Node node)
{
// Base Case
if (node == null)
return 0;
// Recursive call to calculate the
// length of longest path
int left = lengthOfLongestPath(node.left);
int right = lengthOfLongestPath(node.right);
return 1 + (left > right ? left : right);
}
// Function to copy the complete
// path in a matrix
static void copyPath(int[] path, int index,
int[][] mtrx, int r)
{
// Loop to copy the path
for(int i = 0; i < index; i++)
{
mtrx[r][i] = path[i];
}
}
// Function to store all path
// one by one in matrix
static void storePath(Node node, int[] path,
int index, int[][] mtrx)
{
// Base condition
if (node == null)
{
return;
}
// Inserting the current node
// into the current path
path[index] = node.key;
// Recursive call for
// the left sub tree
storePath(node.left, path,
index + 1, mtrx);
// Recursive call for
// the right sub tree
storePath(node.right, path,
index + 1, mtrx);
// Condition to check that current
// node is a leaf node or not
if (node.left == null &&
node.right == null)
{
// Incrementation for changing
// row
row = row + 1;
// Function call for copying
// the path
copyPath(path, index + 1, mtrx, row);
}
}
// Function to calculate
// total path
static int totalPath(Node node)
{
if (node == null)
{
return count;
}
if (node.left == null &&
node.right == null)
{
return count + 1;
}
count = totalPath(node.left);
return totalPath(node.right);
}
// Function for Clockwise Spiral Traversal
// of Binary Tree
static void traverse_matrix(int[][] mtrx,
int height,
int width)
{
int j = 0, k1 = 0, k2 = 0;
int k3 = height - 1;
int k4 = width - 1;
for(int round = 0;
round < height / 2;
round++)
{
for(j = k2; j < width; j++)
{
// Only print those values which
// are not MAX_INTEGER
if (mtrx[k1][j] != Integer.MAX_VALUE)
{
System.out.print(mtrx[k1][j] + " ");
}
}
System.out.println();
k2 = 0;
k1++;
for(j = k4; j >= 0; j--)
{
// Only print those values which
// are not MAX_INTEGER
if (mtrx[k3][j] != Integer.MAX_VALUE)
{
System.out.print(mtrx[k3][j] + " ");
}
}
System.out.println();
k4 = width - 1;
k3--;
}
// Condition (one row may be left
// traversing)
// If number of rows in matrix are odd
if (height % 2 != 0)
{
for(j = k2; j < width; j++)
{
// Only print those values which are
// not MAX_INTEGER
if (mtrx[k1][j] != Integer.MAX_VALUE)
{
System.out.print(mtrx[k1][j] + " ");
}
}
}
}
// Function to print all the paths
// in Boundary Root to Leaf
// Path Traversal
static void PrintPath(Node node)
{
// Calculate the length of
// longest path of the tree
int max_len = lengthOfLongestPath(node);
// Calculate total path
int total_path = totalPath(node);
// Array to store path
int[] path = new int[max_len];
Arrays.fill(path, 0);
// Use double pointer to create
// 2D array which will contain
// all path of the tree
int[][] mtrx = new int[total_path][max_len];
// Initialize complete matrix with
// MAX INTEGER(purpose garbage)
for(int i = 0; i < total_path; i++)
{
for(int j = 0; j < max_len; j++)
{
mtrx[i][j] = Integer.MAX_VALUE;
}
}
row = -1;
storePath(node, path, 0, mtrx);
// Print the circular clockwise spiral
// traversal of the tree
traverse_matrix(mtrx, total_path, max_len);
}
// Driver Code
public static void main(String[] args)
{
/* 10
/ \
13 11
/ \
19 23
/ \ / \
21 29 43 15
/
7 */
// Create Binary Tree as shown
Node root = newNode(10);
root.left = newNode(13);
root.right = newNode(11);
root.right.left = newNode(19);
root.right.right = newNode(23);
root.right.left.left = newNode(21);
root.right.left.right = newNode(29);
root.right.right.left = newNode(43);
root.right.right.right = newNode(15);
root.right.right.right.left = newNode(7);
// Function Call
PrintPath(root);
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 implementation to print the # path in Boundary Root to Leaf # Path Traversal. # Structure of tree node class Node: def __init__(self, key): self.key = key self.left = None self.right = None row = 0 count = 0 # Utility function to # create a new node def newNode(key): temp = Node(key) return temp # Function to calculate the length # of longest path of the tree def lengthOfLongestPath(node): # Base Case if (node == None): return 0; # Recursive call to calculate the length # of longest path left = lengthOfLongestPath(node.left); right = lengthOfLongestPath(node.right); return 1 + (left if left > right else right); # Function to copy the complete # path in a matrix def copyPath(path, index, mtrx, r): # Loop to copy the path for i in range(index): mtrx[r][i] = path[i]; # Function to store all path # one by one in matrix def storePath(node, path, index, mtrx): global row # Base condition if (node == None): return; # Inserting the current node # into the current path path[index] = node.key; # Recursive call for # the left sub tree storePath(node.left, path, index + 1, mtrx); # Recursive call for # the right sub tree storePath(node.right, path, index + 1, mtrx); # Condition to check that current # node is a leaf node or not if (node.left == None and node.right == None): # Incrementation for changing # row row = row + 1; # Function call for copying # the path copyPath(path, index + 1, mtrx, row); # Function to calculate # total path def totalPath(node): global count if (node == None): return count; if (node.left == None and node.right == None): return count + 1; count = totalPath(node.left); return totalPath(node.right); # Function for Clockwise Spiral Traversal # of Binary Tree def traverse_matrix( mtrx, height, width): j = 0 k1 = 0 k2 = 0; k3 = height - 1; k4 = width - 1; for round in range(height//2): for j in range(k2, width): # Only print those values which # are not MAX_INTEGER if (mtrx[k1][j] != 1000000): print(mtrx[k1][j], end=' ') print() k2 = 0; k1 += 1 for j in range(k4, -1, -1): # Only print those values which # are not MAX_INTEGER if (mtrx[k3][j] != 1000000): print(mtrx[k3][j], end=' ') print() k4 = width - 1; k3 -= 1 # Condition (one row may be left # traversing) # If number of rows in matrix are odd if (height % 2 != 0): for j in range(k2, width): # Only print those values which are # not MAX_INTEGER if (mtrx[k1][j] != 1000000): print(mtrx[k1][j], end=' ') # Function to print all the paths # in Boundary Root to Leaf # Path Traversal def PrintPath(node): global row # Calculate the length of # longest path of the tree max_len = lengthOfLongestPath(node); # Calculate total path total_path = totalPath(node); # Array to store path path = [0 for i in range(max_len)] # Use double pointer to create # 2D array which will contain # all path of the tree mtrx = [[1000000 for j in range(max_len)] for i in range(total_path)] row = -1; storePath(node, path, 0, mtrx); # Print the circular clockwise spiral # traversal of the tree traverse_matrix(mtrx, total_path, max_len); # Driver Code if __name__=='__main__': ''' 10 / \ 13 11 / \ 19 23 / \ / \ 21 29 43 15 / 7 ''' # Create Binary Tree as shown root = newNode(10); root.left = newNode(13); root.right = newNode(11); root.right.left = newNode(19); root.right.right = newNode(23); root.right.left.left = newNode(21); root.right.left.right = newNode(29); root.right.right.left = newNode(43); root.right.right.right = newNode(15); root.right.right.right.left = newNode(7); # Function Call PrintPath(root); # This code is contributed by pratham76
C#
// C# implementation to print the
// path in Boundary Root to Leaf
// Path Traversal.
using System;
using System.Collections;
class GFG{
static int row;
static int count = 0;
// Structure of tree node
public class Node
{
public int key;
public Node left, right;
};
// Utility function to
// create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Function to calculate the length
// of longest path of the tree
static int lengthOfLongestPath(Node node)
{
// Base Case
if (node == null)
return 0;
// Recursive call to calculate the
// length of longest path
int left = lengthOfLongestPath(node.left);
int right = lengthOfLongestPath(node.right);
return 1 + (left > right ? left : right);
}
// Function to copy the complete
// path in a matrix
static void copyPath(int[] path, int index,
int[,] mtrx, int r)
{
// Loop to copy the path
for(int i = 0; i < index; i++)
{
mtrx[r, i] = path[i];
}
}
// Function to store all path
// one by one in matrix
static void storePath(Node node, int[] path,
int index, int[,] mtrx)
{
// Base condition
if (node == null)
{
return;
}
// Inserting the current node
// into the current path
path[index] = node.key;
// Recursive call for
// the left sub tree
storePath(node.left, path,
index + 1, mtrx);
// Recursive call for
// the right sub tree
storePath(node.right, path,
index + 1, mtrx);
// Condition to check that current
// node is a leaf node or not
if (node.left == null &&
node.right == null)
{
// Incrementation for changing
// row
row = row + 1;
// Function call for copying
// the path
copyPath(path, index + 1, mtrx, row);
}
}
// Function to calculate
// total path
static int totalPath(Node node)
{
if (node == null)
{
return count;
}
if (node.left == null &&
node.right == null)
{
return count + 1;
}
count = totalPath(node.left);
return totalPath(node.right);
}
// Function for Clockwise Spiral Traversal
// of Binary Tree
static void traverse_matrix(int[,] mtrx,
int height,
int width)
{
int j = 0, k1 = 0, k2 = 0;
int k3 = height - 1;
int k4 = width - 1;
for(int round = 0;
round < height / 2;
round++)
{
for(j = k2; j < width; j++)
{
// Only print those values which
// are not MAX_INTEGER
if (mtrx[k1, j] != 10000000)
{
Console.Write(mtrx[k1, j] + " ");
}
}
Console.WriteLine();
k2 = 0;
k1++;
for(j = k4; j >= 0; j--)
{
// Only print those values which
// are not MAX_INTEGER
if (mtrx[k3, j] != 10000000)
{
Console.Write(mtrx[k3, j] + " ");
}
}
Console.WriteLine();
k4 = width - 1;
k3--;
}
// Condition (one row may be left
// traversing)
// If number of rows in matrix are odd
if (height % 2 != 0)
{
for(j = k2; j < width; j++)
{
// Only print those values which are
// not MAX_INTEGER
if (mtrx[k1, j] != 10000000)
{
Console.Write(mtrx[k1, j] + " ");
}
}
}
}
// Function to print all the paths
// in Boundary Root to Leaf
// Path Traversal
static void PrintPath(Node node)
{
// Calculate the length of
// longest path of the tree
int max_len = lengthOfLongestPath(node);
// Calculate total path
int total_path = totalPath(node);
// Array to store path
int[] path = new int[max_len];
Array.Fill(path, 0);
// Use double pointer to create
// 2D array which will contain
// all path of the tree
int[,] mtrx = new int[total_path, max_len];
// Initialize complete matrix with
// MAX INTEGER(purpose garbage)
for(int i = 0; i < total_path; i++)
{
for(int j = 0; j < max_len; j++)
{
mtrx[i, j] = 10000000;
}
}
row = -1;
storePath(node, path, 0, mtrx);
// Print the circular clockwise spiral
// traversal of the tree
traverse_matrix(mtrx, total_path, max_len);
}
// Driver Code
public static void Main(string[] args)
{
/* 10
/ \
13 11
/ \
19 23
/ \ / \
21 29 43 15
/
7 */
// Create Binary Tree as shown
Node root = newNode(10);
root.left = newNode(13);
root.right = newNode(11);
root.right.left = newNode(19);
root.right.right = newNode(23);
root.right.left.left = newNode(21);
root.right.left.right = newNode(29);
root.right.right.left = newNode(43);
root.right.right.right = newNode(15);
root.right.right.right.left = newNode(7);
// Function Call
PrintPath(root);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript implementation to print the
// path in Boundary Root to Leaf
// Path Traversal.
let row;
let count = 0;
// Structure of tree node
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.key = key;
}
}
// Utility function to
// create a new node
function newNode(key)
{
let temp = new Node(key);
return (temp);
}
// Function to calculate the length
// of longest path of the tree
function lengthOfLongestPath(node)
{
// Base Case
if (node == null)
return 0;
// Recursive call to calculate the
// length of longest path
let left = lengthOfLongestPath(node.left);
let right = lengthOfLongestPath(node.right);
return 1 + (left > right ? left : right);
}
// Function to copy the complete
// path in a matrix
function copyPath(path, index, mtrx, r)
{
// Loop to copy the path
for(let i = 0; i < index; i++)
{
mtrx[r][i] = path[i];
}
}
// Function to store all path
// one by one in matrix
function storePath(node, path, index, mtrx)
{
// Base condition
if (node == null)
{
return;
}
// Inserting the current node
// into the current path
path[index] = node.key;
// Recursive call for
// the left sub tree
storePath(node.left, path,
index + 1, mtrx);
// Recursive call for
// the right sub tree
storePath(node.right, path,
index + 1, mtrx);
// Condition to check that current
// node is a leaf node or not
if (node.left == null &&
node.right == null)
{
// Incrementation for changing
// row
row = row + 1;
// Function call for copying
// the path
copyPath(path, index + 1, mtrx, row);
}
}
// Function to calculate
// total path
function totalPath(node)
{
if (node == null)
{
return count;
}
if (node.left == null &&
node.right == null)
{
return count + 1;
}
count = totalPath(node.left);
return totalPath(node.right);
}
// Function for Clockwise Spiral Traversal
// of Binary Tree
function traverse_matrix(mtrx, height, width)
{
let j = 0, k1 = 0, k2 = 0;
let k3 = height - 1;
let k4 = width - 1;
for(let round = 0; round < parseInt(height / 2, 10);
round++)
{
for(j = k2; j < width; j++)
{
// Only print those values which
// are not MAX_INTEGER
if (mtrx[k1][j] != Number.MAX_VALUE)
{
document.write(mtrx[k1][j] + " ");
}
}
document.write("</br>");
k2 = 0;
k1++;
for(j = k4; j >= 0; j--)
{
// Only print those values which
// are not MAX_INTEGER
if (mtrx[k3][j] != Number.MAX_VALUE)
{
document.write(mtrx[k3][j] + " ");
}
}
document.write("</br>");
k4 = width - 1;
k3--;
}
// Condition (one row may be left
// traversing)
// If number of rows in matrix are odd
if (height % 2 != 0)
{
for(j = k2; j < width; j++)
{
// Only print those values which are
// not MAX_INTEGER
if (mtrx[k1][j] != Number.MAX_VALUE)
{
document.write(mtrx[k1][j] + " ");
}
}
}
}
// Function to print all the paths
// in Boundary Root to Leaf
// Path Traversal
function PrintPath(node)
{
// Calculate the length of
// longest path of the tree
let max_len = lengthOfLongestPath(node);
// Calculate total path
let total_path = totalPath(node);
// Array to store path
let path = new Array(max_len);
path.fill(0);
// Use double pointer to create
// 2D array which will contain
// all path of the tree
let mtrx = new Array(total_path);
// Initialize complete matrix with
// MAX INTEGER(purpose garbage)
for(let i = 0; i < total_path; i++)
{
mtrx[i] = new Array(max_len);
for(let j = 0; j < max_len; j++)
{
mtrx[i][j] = Number.MAX_VALUE;
}
}
row = -1;
storePath(node, path, 0, mtrx);
// Print the circular clockwise spiral
// traversal of the tree
traverse_matrix(mtrx, total_path, max_len);
}
/* 10
/ \
13 11
/ \
19 23
/ \ / \
21 29 43 15
/
7 */
// Create Binary Tree as shown
let root = newNode(10);
root.left = newNode(13);
root.right = newNode(11);
root.right.left = newNode(19);
root.right.right = newNode(23);
root.right.left.left = newNode(21);
root.right.left.right = newNode(29);
root.right.right.left = newNode(43);
root.right.right.right = newNode(15);
root.right.right.right.left = newNode(7);
// Function Call
PrintPath(root);
</script>
Producción:
10 13 7 15 23 11 10 10 11 19 21 43 23 11 10 10 11 19 29
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA