Рубрики

Путь минимальной суммы между двумя листьями двоичного дерева

Деревья, Структуры данных

Дано двоичное дерево, в котором каждый элемент узла содержит число. Задача состоит в том, чтобы найти минимально возможную сумму от одного конечного узла к другому.

Если одна сторона корня пуста, функция должна вернуть минус бесконечность.

Примеры:

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

Подход: идея состоит в том, чтобы поддерживать два значения в рекурсивных вызовах:

  1. Минимальная сумма корневого пути для поддерева, укорененного в текущем узле.
  2. Минимальная сумма пути между листьями.

Для каждого посещенного узла X мы находим минимальную сумму от корня до листа в левом и правом поддеревьях X. Мы добавляем два значения с данными X и сравниваем сумму с текущей минимальной суммой пути.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для поиска минимальной суммы пути
// между двумя листьями двоичного дерева
#include <bits/stdc++.h>

using namespace std;

  
// Узел двоичного дерева

struct Node {

    int data;

    struct Node* left;

    struct Node* right;

};

  
// Утилита для выделения памяти
// для нового узла

struct Node* newNode(int data)

{

    struct Node* node = new (struct Node);

    node->data = data;

    node->left = node->right = NULL;

  

    return (node);

}

  
// Функция полезности, чтобы найти минимальную сумму между
// любые два листа. Эта функция вычисляет два значения:
// 1. Минимальная сумма пути между двумя листами, которая хранится
// в результате и,
// 2. Минимальная сумма от корня до листа, которая возвращается.
// Если одна сторона корня пуста, то она возвращает INT_MIN

int minPathSumUtil(struct Node* root, int& result)

{

    // Базовые случаи

    if (root == NULL)

        return 0;

  

    if (root->left == NULL && root->right == NULL)

        return root->data;

  

    // Находим минимальную сумму в левом и правом поддереве. Также

    // найти минимальную сумму от корня до листа слева и справа

    // вложенные деревья и сохраняем их в ls и rs

    int ls = minPathSumUtil(root->left, result);

    int rs = minPathSumUtil(root->right, result);

  

    // Если существуют оба левых и правых потомка

    if (root->left && root->right) {

        // Обновить результат, если необходимо

        result = min(result, ls + rs + root->data);

  

        // Возвращаем минимально возможное значение для корневого существа

        // на одной стороне

        return min(ls + root->data, rs + root->data);

    }

  

    // Если какой-либо из двух детей пуст, возвращаем

    // корневая сумма для корня, находящегося на одной стороне

    if (root->left == NULL)

        return rs + root->data;

    else

        return ls + root->data;

}

  
// Функция для возврата минимума
// суммируем путь между двумя листьями

int minPathSum(struct Node* root)

{

    int result = INT_MAX;

    minPathSumUtil(root, result);

    return result;

}

  
// Код драйвера

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 программа для поиска минимальной суммы пути
// между двумя листьями двоичного дерева

class GFG

{

      
// Узел двоичного дерева

static class Node 

{ 

    int data; 

    Node left; 

    Node right; 

}; 

  
// Утилита для выделения памяти
// для нового узла

static Node newNode(int data) 

{ 

    Node node = new Node(); 

    node.data = data; 

    node.left = node.right = null; 

  

    return (node); 

} 

static int result;

  
// Функция полезности, чтобы найти минимальную сумму между
// любые два листа. Эта функция вычисляет два значения:
// 1. Минимальная сумма пути между двумя листами, которая хранится
// в результате и,
// 2. Минимальная сумма от корня до листа, которая возвращается.
// Если одна сторона корня пуста, то она возвращает INT_MIN

static int minPathSumUtil( Node root) 

{ 

    // Базовые случаи

    if (root == null) 

        return 0; 

  

    if (root.left == null && root.right == null) 

        return root.data; 

  

    // Находим минимальную сумму в левом и правом поддереве. Также

    // найти минимальную сумму от корня до листа слева и справа

    // вложенные деревья и сохраняем их в ls и rs

    int ls = minPathSumUtil(root.left); 

    int rs = minPathSumUtil(root.right); 

  

    // Если существуют оба левых и правых потомка

    if (root.left != null && root.right != null) 

    { 

        // Обновить результат, если необходимо

        result = Math.min(result, ls + rs + root.data); 

  

        // Возвращаем минимально возможное значение для корневого существа

        // на одной стороне

        return Math.min(ls + root.data, rs + root.data); 

    } 

  

    // Если какой-либо из двух детей пуст, возвращаем

    // корневая сумма для корня, находящегося на одной стороне

    if (root.left == null) 

        return rs + root.data; 

    else

        return ls + root.data; 

} 

  
// Функция для возврата минимума
// суммируем путь между двумя листьями

static int minPathSum( Node root) 

{ 

    result = Integer.MAX_VALUE; 

    minPathSumUtil(root); 

    return result; 

} 

  

  
// Код драйвера

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)); 

}
} 

  
// Этот код предоставлен Арнабом Кунду

python3

# Python3 программа для поиска минимальной суммы пути
# между двумя листьями двоичного дерева

      
# Узел дерева

class Node: 

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

  
# Сервисная функция для выделения памяти
# для нового узла

def newNode( data): 

  

    node = Node(0) 

    node.data = data 

    node.left = node.right = None

  

    return (node) 

  

result = -1

  
# Полезная функция для поиска
# минимальная сумма между любыми двумя листьями.
# Эта функция вычисляет два значения:
# 1. Минимальная сумма пути между двумя листьями
# который сохраняется в результате и,
# 2. Минимальная сумма от корня до листа
# который возвращается.
# Если одна сторона корня пуста,
# тогда возвращается INT_MIN

def minPathSumUtil(root) :

    global result

      

    # Базовые случаи

    if (root == None): 

        return 0

  

    if (root.left == None and 

        root.right == None) :

        return root.data 

  

    # Найти минимальную сумму в левом и правом поддереве.

    # Также найдите минимальную сумму от корня до листа в

    # левые и правые поддеревья и сохраняйте их

    # в лс и rs

    ls = minPathSumUtil(root.left) 

    rs = minPathSumUtil(root.right) 

  

    # Если существуют левые и правые дети

    if (root.left != None and 

        root.right != None) :

      

        # Обновить результат при необходимости

        result = min(result, ls + 

                     rs + root.data) 

  

        # Вернуть минимально возможное значение для

        # корень на одной стороне

        return min(ls + root.data, 

                   rs + root.data) 

      

    # Если любой из двух детей пуст,

    # вернуть сумму корня для корня, находящегося на одной стороне

    if (root.left == None) :

        return rs + root.data 

    else:

        return ls + root.data 

  
# Функция для возврата минимума
# сумма пути между двумя листьями

def minPathSum( root): 

    global result

    result = 9999999

    minPathSumUtil(root) 

    return result 

  
# Код драйвера

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)) 

  
# Этот код добавлен
# Арнаб Кунду

C #

// C # программа для поиска минимальной суммы пути
// между двумя листьями двоичного дерева

using System;

      

class GFG

{

      
// Узел двоичного дерева

public class Node 

{ 

    public int data; 

    public Node left; 

    public Node right; 

}; 

  
// Утилита для выделения памяти
// для нового узла

static Node newNode(int data) 

{ 

    Node node = new Node(); 

    node.data = data; 

    node.left = node.right = null; 

  

    return (node); 

} 

static int result;

  
// Функция полезности, чтобы найти минимальную сумму между
// любые два листа. Эта функция вычисляет два значения:
// 1. Минимальная сумма пути между двумя листами, которая хранится
// в результате и,
// 2. Минимальная сумма от корня до листа, которая возвращается.
// Если одна сторона корня пуста, то она возвращает INT_MIN

static int minPathSumUtil( Node root) 

{ 

    // Базовые случаи

    if (root == null) 

        return 0; 

  

    if (root.left == null && root.right == null) 

        return root.data; 

  

    // Находим минимальную сумму в левом и правом поддереве. Также

    // найти минимальную сумму от корня до листа слева и справа

    // вложенные деревья и сохраняем их в ls и rs

    int ls = minPathSumUtil(root.left); 

    int rs = minPathSumUtil(root.right); 

  

    // Если существуют оба левых и правых потомка

    if (root.left != null && root.right != null) 

    { 

        // Обновить результат, если необходимо

        result = Math.Min(result, ls + rs + root.data); 

  

        // Возвращаем минимально возможное значение для корневого существа

        // на одной стороне

        return Math.Min(ls + root.data, rs + root.data); 

    } 

  

    // Если какой-либо из двух детей пуст, возвращаем

    // корневая сумма для корня, находящегося на одной стороне

    if (root.left == null) 

        return rs + root.data; 

    else

        return ls + root.data; 

} 

  
// Функция для возврата минимума
// суммируем путь между двумя листьями

static int minPathSum( Node root) 

{ 

    result = int.MaxValue; 

    minPathSumUtil(root); 

    return result; 

} 

  

  
// Код драйвера

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)); 
}
}

  
// Этот код предоставлен 29AjayKumar

Выход:

1

Рекомендуемые посты:

Путь минимальной суммы между двумя листьями двоичного дерева

0.00 (0%) 0 votes