Dado un árbol binario en el que cada elemento de Node contiene un número. La tarea es encontrar la suma mínima posible de un Node hoja a otro.
Si un lado de la raíz está vacío, entonces la función debería devolver menos infinito.
Ejemplos:
Input :
4
/ \
5 -6
/ \ / \
2 -3 1 8
Output : 1
The minimum sum path between two leaf nodes is:
-3 -> 5 -> 4 -> -6 -> 1
Input :
3
/ \
2 4
/ \
-5 1
Output : -2
Enfoque: La idea es mantener dos valores en las llamadas recursivas:
- Suma mínima de ruta de raíz a hoja para el subárbol enraizado en el Node actual.
- La suma mínima de caminos entre hojas.
Para cada Node X visitado, encontramos la suma mínima de raíz a hoja en los subárboles izquierdo y derecho de X. Agregamos los dos valores con los datos de X y comparamos la suma con la suma de ruta mínima actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find minimum path sum
// between two leaves of a binary tree
#include <bits/stdc++.h>
using namespace std;
// A binary tree node
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Utility function to allocate memory
// for a new node
struct Node* newNode(int data)
{
struct Node* node = new (struct Node);
node->data = data;
node->left = node->right = NULL;
return (node);
}
// A utility function to find the minimum sum between
// any two leaves. This function calculates two values:
// 1. Minimum path sum between two leaves which is stored
// in result and,
// 2. The minimum root to leaf path sum which is returned.
// If one side of root is empty, then it returns INT_MIN
int minPathSumUtil(struct Node* root, int& result)
{
// Base cases
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return root->data;
// Find minimum sum in left and right sub tree. Also
// find minimum root to leaf sums in left and right
// sub trees and store them in ls and rs
int ls = minPathSumUtil(root->left, result);
int rs = minPathSumUtil(root->right, result);
// If both left and right children exist
if (root->left && root->right) {
// Update result if needed
result = min(result, ls + rs + root->data);
// Return minimum possible value for root being
// on one side
return min(ls + root->data, rs + root->data);
}
// If any of the two children is empty, return
// root sum for root being on one side
if (root->left == NULL)
return rs + root->data;
else
return ls + root->data;
}
// Function to return the minimum
// sum path between two leaves
int minPathSum(struct Node* root)
{
int result = INT_MAX;
minPathSumUtil(root, result);
return result;
}
// Driver code
int main()
{
struct Node* root = newNode(4);
root->left = newNode(5);
root->right = newNode(-6);
root->left->left = newNode(2);
root->left->right = newNode(-3);
root->right->left = newNode(1);
root->right->right = newNode(8);
cout << minPathSum(root);
return 0;
}
Java
// Java program to find minimum path sum
// between two leaves of a binary tree
class GFG
{
// A binary tree node
static class Node
{
int data;
Node left;
Node right;
};
// Utility function to allocate memory
// for a new node
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
static int result;
// A utility function to find the minimum sum between
// any two leaves. This function calculates two values:
// 1. Minimum path sum between two leaves which is stored
// in result and,
// 2. The minimum root to leaf path sum which is returned.
// If one side of root is empty, then it returns INT_MIN
static int minPathSumUtil( Node root)
{
// Base cases
if (root == null)
return 0;
if (root.left == null && root.right == null)
return root.data;
// Find minimum sum in left and right sub tree. Also
// find minimum root to leaf sums in left and right
// sub trees and store them in ls and rs
int ls = minPathSumUtil(root.left);
int rs = minPathSumUtil(root.right);
// If both left and right children exist
if (root.left != null && root.right != null)
{
// Update result if needed
result = Math.min(result, ls + rs + root.data);
// Return minimum possible value for root being
// on one side
return Math.min(ls + root.data, rs + root.data);
}
// If any of the two children is empty, return
// root sum for root being on one side
if (root.left == null)
return rs + root.data;
else
return ls + root.data;
}
// Function to return the minimum
// sum path between two leaves
static int minPathSum( Node root)
{
result = Integer.MAX_VALUE;
minPathSumUtil(root);
return result;
}
// Driver code
public static void main(String args[])
{
Node root = newNode(4);
root.left = newNode(5);
root.right = newNode(-6);
root.left.left = newNode(2);
root.left.right = newNode(-3);
root.right.left = newNode(1);
root.right.right = newNode(8);
System.out.print(minPathSum(root));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to find minimum path sum # between two leaves of a binary tree # Tree node class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Utility function to allocate memory # for a new node def newNode( data): node = Node(0) node.data = data node.left = node.right = None return (node) result = -1 # A utility function to find the # minimum sum between any two leaves. # This function calculates two values: # 1. Minimum path sum between two leaves # which is stored in result and, # 2. The minimum root to leaf path sum # which is returned. # If one side of root is empty, # then it returns INT_MIN def minPathSumUtil(root) : global result # Base cases if (root == None): return 0 if (root.left == None and root.right == None) : return root.data # Find minimum sum in left and right sub tree. # Also find minimum root to leaf sums in # left and right sub trees and store them # in ls and rs ls = minPathSumUtil(root.left) rs = minPathSumUtil(root.right) # If both left and right children exist if (root.left != None and root.right != None) : # Update result if needed result = min(result, ls + rs + root.data) # Return minimum possible value for # root being on one side return min(ls + root.data, rs + root.data) # If any of the two children is empty, # return root sum for root being on one side if (root.left == None) : return rs + root.data else: return ls + root.data # Function to return the minimum # sum path between two leaves def minPathSum( root): global result result = 9999999 minPathSumUtil(root) return result # Driver code root = newNode(4) root.left = newNode(5) root.right = newNode(-6) root.left.left = newNode(2) root.left.right = newNode(-3) root.right.left = newNode(1) root.right.right = newNode(8) print(minPathSum(root)) # This code is contributed # by Arnab Kundu
C#
// C# program to find minimum path sum
// between two leaves of a binary tree
using System;
class GFG
{
// A binary tree node
public class Node
{
public int data;
public Node left;
public Node right;
};
// Utility function to allocate memory
// for a new node
static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}
static int result;
// A utility function to find the minimum sum between
// any two leaves. This function calculates two values:
// 1. Minimum path sum between two leaves which is stored
// in result and,
// 2. The minimum root to leaf path sum which is returned.
// If one side of root is empty, then it returns INT_MIN
static int minPathSumUtil( Node root)
{
// Base cases
if (root == null)
return 0;
if (root.left == null && root.right == null)
return root.data;
// Find minimum sum in left and right sub tree. Also
// find minimum root to leaf sums in left and right
// sub trees and store them in ls and rs
int ls = minPathSumUtil(root.left);
int rs = minPathSumUtil(root.right);
// If both left and right children exist
if (root.left != null && root.right != null)
{
// Update result if needed
result = Math.Min(result, ls + rs + root.data);
// Return minimum possible value for root being
// on one side
return Math.Min(ls + root.data, rs + root.data);
}
// If any of the two children is empty, return
// root sum for root being on one side
if (root.left == null)
return rs + root.data;
else
return ls + root.data;
}
// Function to return the minimum
// sum path between two leaves
static int minPathSum( Node root)
{
result = int.MaxValue;
minPathSumUtil(root);
return result;
}
// Driver code
public static void Main(String []args)
{
Node root = newNode(4);
root.left = newNode(5);
root.right = newNode(-6);
root.left.left = newNode(2);
root.left.right = newNode(-3);
root.right.left = newNode(1);
root.right.right = newNode(8);
Console.Write(minPathSum(root));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to find minimum path sum
// between two leaves of a binary tree
// Structure of binary tree
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Utility function to allocate memory
// for a new node
function newNode(data)
{
let node = new Node(data);
return (node);
}
let result;
// A utility function to find the minimum sum between
// any two leaves. This function calculates two values:
// 1. Minimum path sum between two leaves which is stored
// in result and,
// 2. The minimum root to leaf path sum which is returned.
// If one side of root is empty, then it returns INT_MIN
function minPathSumUtil(root)
{
// Base cases
if (root == null)
return 0;
if (root.left == null && root.right == null)
return root.data;
// Find minimum sum in left and right sub tree. Also
// find minimum root to leaf sums in left and right
// sub trees and store them in ls and rs
let ls = minPathSumUtil(root.left);
let rs = minPathSumUtil(root.right);
// If both left and right children exist
if (root.left != null && root.right != null)
{
// Update result if needed
result = Math.min(result, ls + rs + root.data);
// Return minimum possible value for root being
// on one side
return Math.min(ls + root.data, rs + root.data);
}
// If any of the two children is empty, return
// root sum for root being on one side
if (root.left == null)
return rs + root.data;
else
return ls + root.data;
}
// Function to return the minimum
// sum path between two leaves
function minPathSum(root)
{
result = Number.MAX_VALUE;
minPathSumUtil(root);
return result;
}
let root = newNode(4);
root.left = newNode(5);
root.right = newNode(-6);
root.left.left = newNode(2);
root.left.right = newNode(-3);
root.right.left = newNode(1);
root.right.right = newNode(8);
document.write(minPathSum(root));
</script>
Producción:
1
Complejidad temporal : O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA