Dado un árbol binario y una suma S , imprima todas las rutas, comenzando desde la raíz, que suman hasta la suma dada.
Tenga en cuenta que este problema es diferente de las rutas de la raíz a la hoja . Aquí la ruta no necesita terminar en un Node hoja.
Ejemplos:
Input :
Input : sum = 8,
Root of tree
1
/ \
20 3
/ \
4 15
/ \ / \
6 7 8 9
Output :
Path: 1 3 4
Input : sum = 38,
Root of tree
10
/ \
28 13
/ \
14 15
/ \ / \
21 22 23 24
Output : Path found: 10 28
Path found: 10 13 15
Para este problema, el recorrido previo al pedido es el más adecuado, ya que tenemos que sumar un valor clave cuando aterrizamos en ese Node.
Comenzamos desde la raíz y comenzamos a atravesar por orden previo, agregando valor clave a sum_so_far y verificando si es igual a la suma requerida.
Además, como el Node del árbol no tiene un puntero que apunte a su padre, tenemos que guardar explícitamente desde donde nos hemos movido. Usamos una ruta vectorial para almacenar la ruta para esto.
Cada Node en esta ruta contribuye a sum_so_far.
Implementación:
C++
// C++ program to print all paths beginning with
// root and sum as given sum
#include<bits/stdc++.h>
using namespace std;
// A 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);
}
void printPathsUtil(Node* curr_node, int sum,
int sum_so_far, vector<int> &path)
{
if (curr_node == NULL)
return;
// add the current node's value
sum_so_far += curr_node->key;
// add the value to path
path.push_back(curr_node->key);
// print the required path
if (sum_so_far == sum )
{
cout << "Path found: ";
for (int i=0; i<path.size(); i++)
cout << path[i] << " ";
cout << endl;
}
// if left child exists
if (curr_node->left != NULL)
printPathsUtil(curr_node->left, sum, sum_so_far, path);
// if right child exists
if (curr_node->right != NULL)
printPathsUtil(curr_node->right, sum, sum_so_far, path);
// Remove last element from path
// and move back to parent
path.pop_back();
}
// Wrapper over printPathsUtil
void printPaths(Node *root, int sum)
{
vector<int> path;
printPathsUtil(root, sum, 0, path);
}
// Driver program
int main ()
{
/* 10
/ \
28 13
/ \
14 15
/ \ / \
21 22 23 24*/
Node *root = newNode(10);
root->left = newNode(28);
root->right = newNode(13);
root->right->left = newNode(14);
root->right->right = newNode(15);
root->right->left->left = newNode(21);
root->right->left->right = newNode(22);
root->right->right->left = newNode(23);
root->right->right->right = newNode(24);
int sum = 38;
printPaths(root, sum);
return 0;
}
Java
// Java program to print all paths beginning
// with root and sum as given sum
import java.util.ArrayList;
class Graph{
// A 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);
}
static void printPathsUtil(Node curr_node, int sum,
int sum_so_far,
ArrayList<Integer> path)
{
if (curr_node == null)
return;
// Add the current node's value
sum_so_far += curr_node.key;
// Add the value to path
path.add(curr_node.key);
// Print the required path
if (sum_so_far == sum)
{
System.out.print("Path found: ");
for(int i = 0; i < path.size(); i++)
System.out.print(path.get(i) + " ");
System.out.println();
}
// If left child exists
if (curr_node.left != null)
printPathsUtil(curr_node.left, sum,
sum_so_far, path);
// If right child exists
if (curr_node.right != null)
printPathsUtil(curr_node.right, sum,
sum_so_far, path);
// Remove last element from path
// and move back to parent
path.remove(path.size() - 1);
}
// Wrapper over printPathsUtil
static void printPaths(Node root, int sum)
{
ArrayList<Integer> path = new ArrayList<>();
printPathsUtil(root, sum, 0, path);
}
// Driver code
public static void main(String[] args)
{
/* 10
/ \
28 13
/ \
14 15
/ \ / \
21 22 23 24*/
Node root = newNode(10);
root.left = newNode(28);
root.right = newNode(13);
root.right.left = newNode(14);
root.right.right = newNode(15);
root.right.left.left = newNode(21);
root.right.left.right = newNode(22);
root.right.right.left = newNode(23);
root.right.right.right = newNode(24);
int sum = 38;
printPaths(root, sum);
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 program to Print all the
# paths from root, with a specified
# sum in Binary tree
# Binary Tree Node
""" utility that allocates a newNode
with the given key """
class newNode:
# Construct to create a newNode
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# This function prints all paths
# that have sum k
def printPathsUtil(curr_node, sum,
sum_so_far, path):
# empty node
if (not curr_node) :
return
sum_so_far += curr_node.key
# add current node to the path
path.append(curr_node.key)
# print the required path
if (sum_so_far == sum ) :
print("Path found:", end = " ")
for i in range(len(path)):
print(path[i], end = " ")
print()
# if left child exists
if (curr_node.left != None) :
printPathsUtil(curr_node.left, sum,
sum_so_far, path)
# if right child exists
if (curr_node.right != None) :
printPathsUtil(curr_node.right, sum,
sum_so_far, path)
# Remove the current element
# from the path
path.pop(-1)
# A wrapper over printKPathUtil()
def printPaths(root, sum):
path = []
printPathsUtil(root, sum, 0, path)
# Driver Code
if __name__ == '__main__':
""" 10
/ \
28 13
/ \
14 15
/ \ / \
21 22 23 24"""
root = newNode(10)
root.left = newNode(28)
root.right = newNode(13)
root.right.left = newNode(14)
root.right.right = newNode(15)
root.right.left.left = newNode(21)
root.right.left.right = newNode(22)
root.right.right.left = newNode(23)
root.right.right.right = newNode(24)
sum = 38
printPaths(root, sum)
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
Javascript
<script>
// JavaScript program to print all paths beginning
// with root and sum as given sum
// A Tree node
class Node
{
constructor()
{
this.key = 0;
this.left = null;
this.right = null;
}
};
// Utility function to create a new node
function newNode(key)
{
var temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
function printPathsUtil(curr_node, sum, sum_so_far, path)
{
if (curr_node == null)
return;
// Add the current node's value
sum_so_far += curr_node.key;
// Add the value to path
path.push(curr_node.key);
// Print the required path
if (sum_so_far == sum)
{
document.write("Path found: ");
for(var i = 0; i < path.length; i++)
document.write(path[i] + " ");
document.write("<br>");
}
// If left child exists
if (curr_node.left != null)
printPathsUtil(curr_node.left, sum,
sum_so_far, path);
// If right child exists
if (curr_node.right != null)
printPathsUtil(curr_node.right, sum,
sum_so_far, path);
// Remove last element from path
// and move back to parent
path.pop();
}
// Wrapper over printPathsUtil
function printPaths(root, sum)
{
var path = [];
printPathsUtil(root, sum, 0, path);
}
// Driver code
/* 10
/ \
28 13
/ \
14 15
/ \ / \
21 22 23 24*/
var root = newNode(10);
root.left = newNode(28);
root.right = newNode(13);
root.right.left = newNode(14);
root.right.right = newNode(15);
root.right.left.left = newNode(21);
root.right.left.right = newNode(22);
root.right.right.left = newNode(23);
root.right.right.right = newNode(24);
var sum = 38;
printPaths(root, sum);
</script>
Producción
Path found: 10 28 Path found: 10 13 15
Este artículo es una contribución de Shubham Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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