Dado un árbol binario y un número, la tarea es devolver la longitud del camino más corto que comienza en la raíz y termina en un Node de hoja tal que la suma de los números a lo largo de ese camino sea igual a ‘suma’. Imprima «-1» si no existe tal ruta.
Ejemplos:
Input:
1
/ \
10 15
/ \
5 2
Number = 16
Output: 2
There are two paths:
1->15, length of path is 3
1->10->5, length of path is 2
Input:
1
/ \
10 15
/ \
5 2
Number = 20
Output: -1
There exists no such path with 20 as sum from root to any node
Fuente: Entrevista de Microsoft
Enfoque : En esta publicación se ha discutido un enfoque para comprobar si existe o no una ruta de este tipo . Se pueden seguir los siguientes pasos para encontrar el camino más corto.
- Llame recursivamente al hijo izquierdo y derecho con la suma de la ruta y el nivel a ( número – valor en el Node actual, nivel + 1).
- Si se alcanza el Node hoja, almacene el mínimo de todos los niveles del Node hoja.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to find the shortes path from root
// to leaf with given sum
void hasPathSum(struct Node* node, int sum,
int& mini, int level)
{
// went beyond tree
if (node == NULL)
return;
int subSum = sum - (node->data);
if (node->left == NULL && node->right == NULL) {
// Store the minimum path
if (subSum == 0)
mini = min(level - 1, mini);
return;
}
else {
// Recur in the left tree
hasPathSum(node->left, subSum, mini, level + 1);
// Recur in the right tree
hasPathSum(node->right, subSum, mini, level + 1);
}
}
/* UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct Node* newnode(int data)
{
struct Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return (node);
}
/* Driver program to test above functions*/
int main()
{
int sum = 16;
/* Constructed binary tree is
1
/ \
10 15
/ \
5 2
*/
struct Node* root = newnode(1);
root->left = newnode(10);
root->right = newnode(15);
root->left->left = newnode(5);
root->left->right = newnode(2);
int mini = INT_MAX;
// Function call
hasPathSum(root, sum, mini, 0);
if (mini != INT_MAX)
printf("There is a root-to-leaf path with sum %d\n"
"and the shortest path length is: %d",
sum, mini + 1);
else
printf("There is no root-to-leaf path with sum %d", sum);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
static int mini;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
static class Node
{
int data;
Node left;
Node right;
};
// Function to find the shortes path from root
// to leaf with given sum
static void hasPathSum(Node node, int sum,
int level)
{
// went beyond tree
if (node == null)
return;
int subSum = sum - (node.data);
if (node.left == null && node.right == null)
{
// Store the minimum path
if (subSum == 0)
mini = Math.min(level - 1, mini);
return;
}
else
{
// Recur in the left tree
hasPathSum(node.left, subSum, level + 1);
// Recur in the right tree
hasPathSum(node.right, subSum, level + 1);
}
}
/* UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
static Node newnode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
/* Driver code*/
public static void main(String[] args)
{
int sum = 16;
/* Constructed binary tree is
1
/ \
10 15
/ \
5 2
*/
Node root = newnode(1);
root.left = newnode(10);
root.right = newnode(15);
root.left.left = newnode(5);
root.left.right = newnode(2);
mini = Integer.MAX_VALUE;
// Function call
hasPathSum(root, sum, 0);
if (mini != Integer.MAX_VALUE)
System.out.printf("There is a root-to-leaf path with sum %d\n"
+"and the shortest path length is: %d"
,sum, mini + 1);
else
System.out.printf("There is no root-to-leaf path with sum %d", sum);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the above approach
INT_MAX = 2147483647
""" A binary tree node has data, pointer
to left child and a pointer to right child """
"""UTILITY FUNCTIONS
Helper function that allocates a new node
with the given data and NULL left and right
pointers."""
class newnode:
# Construct to create a newNode
def __init__(self, key):
self.data = key
self.left = None
self.right = None
# Function to find the shortes path
# from root to leaf with given summ
def hasPathSum(node, summ, mini, level) :
# check if leaf node and check summ
if (node == None) :
return
subsumm = summ - node.data
if(node.left == None and node.right == None):
# Store the minimum path
if (subsumm == 0) :
mini[0] = min(level - 1, mini[0])
return
else:
# Recur in the left tree
hasPathSum(node.left, subsumm,
mini, level + 1)
# Recur in the right tree
hasPathSum(node.right, subsumm,
mini, level + 1)
# Driver Code
if __name__ == '__main__':
summ = 16
""" Constructed binary tree is
1
/ \
10 15
/ \ \
5 2 15
"""
root = newnode(1)
root.left = newnode(10)
root.right = newnode(15)
root.left.left = newnode(5)
root.left.right = newnode(2)
mini = [INT_MAX]
# Function call
hasPathSum(root, summ, mini, 0)
if (mini[0] != INT_MAX) :
print("There is a root-to-leaf path",
"with sum", summ)
print("and the shortest path length is:",
mini[0] + 1)
else:
print("There is no root-to-leaf path",
"with sum ", summ)
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# implementation of the above approach
using System;
class GFG
{
static int mini;
/* A binary tree node has data, pointer to left child
and a pointer to right child */
public class Node
{
public int data;
public Node left;
public Node right;
};
// Function to find the shortes path from root
// to leaf with given sum
static void hasPathSum(Node node, int sum,
int level)
{
// went beyond tree
if (node == null)
return;
int subSum = sum - (node.data);
if (node.left == null && node.right == null)
{
// Store the minimum path
if (subSum == 0)
mini = Math.Min(level - 1, mini);
return;
}
else
{
// Recur in the left tree
hasPathSum(node.left, subSum, level + 1);
// Recur in the right tree
hasPathSum(node.right, subSum, level + 1);
}
}
/* UTILITY FUNCTIONS */
/* Helper function that allocates a new node with the
given data and null left and right pointers. */
static Node newnode(int data)
{
Node node = new Node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
/* Driver code*/
public static void Main(String[] args)
{
int sum = 16;
/* Constructed binary tree is
1
/ \
10 15
/ \
5 2
*/
Node root = newnode(1);
root.left = newnode(10);
root.right = newnode(15);
root.left.left = newnode(5);
root.left.right = newnode(2);
mini = int.MaxValue;
// Function call
hasPathSum(root, sum, 0);
if (mini != int.MaxValue)
Console.Write("There is a root-to-leaf path with sum {0}\n"
+"and the shortest path length is: {1}"
,sum, mini + 1);
else
Console.Write("There is no root-to-leaf path with sum {0}", sum);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the
// above approach
/*
* A binary tree node has data,
pointer to left child and a pointer to right
* child
*/
class Node {
constructor() {
this.data = 0;
this.left = null;
this.right = null;
}
}
// Function to find the shortes path from root
// to leaf with given sum
function hasPathSum(node , sum , level) {
// went beyond tree
if (node == null)
return;
var subSum = sum - (node.data);
if (node.left == null && node.right == null) {
// Store the minimum path
if (subSum == 0)
mini = Math.min(level - 1, mini);
return;
}
else {
// Recur in the left tree
hasPathSum(node.left, subSum, level + 1);
// Recur in the right tree
hasPathSum(node.right, subSum, level + 1);
}
}
/* UTILITY FUNCTIONS */
/*
* Helper function that allocates a new node with
the given data and null left
* and right pointers.
*/
function newnode(data) {
var node = new Node();
node.data = data;
node.left = null;
node.right = null;
return (node);
}
/* Driver code */
var sum = 16;
/*
* Constructed binary tree is
*
* 1
/ \
10 15
/ \
5 2
*/
var root = newnode(1);
root.left = newnode(10);
root.right = newnode(15);
root.left.left = newnode(5);
root.left.right = newnode(2);
mini = Number.MAX_VALUE;
// Function call
hasPathSum(root, sum, 0);
if (mini != Number.MAX_VALUE)
document.write(
"There is a root-to-leaf path with sum "+sum+"<br/>" +
"and the shortest path length is: "+(mini + 1));
else
document.write(
"There is no root-to-leaf path with sum "+ sum
);
// This code is contributed by todaysgaurav
</script>
Producción:
There is a root-to-leaf path with sum 16 and the shortest path length is: 1
Complejidad de tiempo: O(N), ya que estamos usando la recursividad para atravesar todos los Nodes del árbol. Donde N es el número de Nodes en el árbol.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.