Рубрики

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

Дано двоичное дерево, в котором каждый элемент узла содержит число. Найдите максимально возможную сумму от одного листового узла до другого.
Путь максимальной суммы может проходить или не проходить через root. Например, в следующем двоичном дереве максимальная сумма равна 27 (3 + 6 + 9 + 0 — 1 + 10). Ожидаемая сложность времени O (n).

Если одна сторона корня пуста, то функция должна возвращать минус бесконечность (INT_MIN в случае C / C ++)

Простое решение состоит в том, чтобы пройти по дереву и выполнить следующее для каждого пройденного узла X.
1) Найти максимальную сумму от листа к корню в левом поддереве X (мы можем использовать этот пост для этого и последующих шагов)
2) Найти максимальную сумму от листа к корню в правом поддереве X.
3) Добавьте вышеупомянутые два вычисленных значения и данные X-> и сравните сумму с максимальным значением, полученным до настоящего времени, и обновите максимальное значение.
4) Вернуть максимальное значение.

Временная сложность вышеуказанного решения составляет O (n 2 )

Мы можем найти максимальную сумму, используя единственный обход двоичного дерева . Идея состоит в том, чтобы поддерживать два значения в рекурсивных вызовах
1) Максимальная сумма пути от корня к листу для поддерева, укорененного в текущем узле.
2) Максимальная сумма пути между листьями (желаемый выход).

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

Ниже приведена реализация вышеуказанного решения O (n).

C ++

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

using namespace std;

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

struct Node

{

    int data;

    struct Node* left, *right;

};

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

struct Node* newNode(int data)

{

    struct Node* node = new(struct Node);

    node->data = data;

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

    return (node);

}

  
// Сервисная функция для поиска максимум двух целых

int max(int a, int b)

{ return (a >= b)? a: b; }

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

int maxPathSumUtil(struct Node *root, int &res)

{

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

    if (root==NULL) return 0;

    if (!root->left && !root->right) return root->data;

  

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

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

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

    int ls = maxPathSumUtil(root->left, res);

    int rs = maxPathSumUtil(root->right, res);

  

  

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

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

    {

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

        res = max(res, ls + rs + root->data);

  

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

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

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

    }

  

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

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

    return (!root->left)? rs + root->data:

                          ls + root->data;

}

  
// Основная функция, которая возвращает сумму максимума
// суммируем путь между двумя листьями. Эта функция в основном
// использует maxPathSumUtil ()

int maxPathSum(struct Node *root)

{

    int res = INT_MIN;

    maxPathSumUtil(root, res);

    return res;

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    struct Node *root = newNode(-15);

    root->left = newNode(5);

    root->right = newNode(6);

    root->left->left = newNode(-8);

    root->left->right = newNode(1);

    root->left->left->left = newNode(2);

    root->left->left->right = newNode(6);

    root->right->left = newNode(3);

    root->right->right = newNode(9);

    root->right->right->right= newNode(0);

    root->right->right->right->left= newNode(4);

    root->right->right->right->right= newNode(-1);

    root->right->right->right->right->left= newNode(10);

    cout << "Max pathSum of the given binary tree is "

         << maxPathSum(root);

    return 0;

}

Джава

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

class Node {

  

    int data;

    Node left, right;

  

    Node(int item) {

        data = item;

        left = right = null;

    }

}

  
// Объект Res передается так, что
// одно и то же значение может использоваться несколькими рекурсивными вызовами.

class Res {

    int val;

}

  

class BinaryTree {

  

    static Node root;

  

    // Функция полезности для поиска максимальной суммы между любыми

    // два листа. Эта функция вычисляет два значения:

    // 1) Максимальная сумма пути между двумя листами, которая хранится

    // в рез.

    // 2) Максимальная сумма пути от корня к листу, которая возвращается.

    // Если одна сторона корня пуста, то она возвращает INT_MIN

    int maxPathSumUtil(Node node, Res res) {

  

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

        if (node == null)

            return 0;

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

            return node.data;

  

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

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

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

        int ls = maxPathSumUtil(node.left, res);

        int rs = maxPathSumUtil(node.right, res);

  

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

        if (node.left != null && node.right != null) {

  

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

            res.val = Math.max(res.val, ls + rs + node.data);

  

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

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

            return Math.max(ls, rs) + node.data;

        }

  

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

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

        return (node.left == null) ? rs + node.data

                : ls + node.data;

    }

  

    // Основная функция, которая возвращает сумму максимума

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

    // использует maxPathSumUtil ()

    int maxPathSum(Node node)

    {

        Res res = new Res();

        res.val = Integer.MIN_VALUE;

        maxPathSumUtil(root, res);

        return res.val;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[]) {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(-15);

        tree.root.left = new Node(5);

        tree.root.right = new Node(6);

        tree.root.left.left = new Node(-8);

        tree.root.left.right = new Node(1);

        tree.root.left.left.left = new Node(2);

        tree.root.left.left.right = new Node(6);

        tree.root.right.left = new Node(3);

        tree.root.right.right = new Node(9);

        tree.root.right.right.right = new Node(0);

        tree.root.right.right.right.left = new Node(4);

        tree.root.right.right.right.right = new Node(-1);

        tree.root.right.right.right.right.left = new Node(10);

        System.out.println("Max pathSum of the given binary tree is "

                + tree.maxPathSum(root));

    }

}

  
// Этот код предоставлен Mayank Jaiswal

питон

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

  

INT_MIN = -2**32

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

class Node:

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

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

  

def maxPathSumUtil(root, res):

      

    # Базовый вариант

    if root is None:

        return 0

      

    if root.left is None and root.right is None:

        return root.data

      

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

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

    # поддеревья и храним их в ls и rs

    ls = maxPathSumUtil(root.left, res)

    rs = maxPathSumUtil(root.right, res)

  

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

    if root.left is not None and root.right is not None:

  

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

        res[0] = max(res[0], ls + rs + root.data)

  

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

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

        return max(ls, rs) + root.data

          

    # Если один из двух детей пуст, вернуть

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

    if root.left is None:

        return rs + root.data

    else:

        return ls + root.data

  
# Основная функция, которая возвращает сумму максимума
# сумма пути между двумя листьями. Эта функция в основном
# использует maxPathSumUtil ()

def maxPathSum(root):

        res = [INT_MIN]

        maxPathSumUtil(root, res)

        return res[0]

  

  
# Программа драйвера для проверки вышеуказанной функции

root = Node(-15)

root.left = Node(5)

root.right = Node(6)

root.left.left = Node(-8)

root.left.right = Node(1)

root.left.left.left = Node(2)

root.left.left.right = Node(6)

root.right.left = Node(3)

root.right.right = Node(9)

root.right.right.right= Node(0)

root.right.right.right.left = Node(4)

root.right.right.right.right = Node(-1)

root.right.right.right.right.left = Node(10)

  

print "Max pathSum of the given binary tree is", maxPathSum(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

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

public class Node

{

  

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  
// Объект Res передается так, что
// одно и то же значение может использоваться несколькими рекурсивными вызовами.

public class Res

{

    public int val;

}

  

public class BinaryTree

{

  

    public static Node root;

  

    // Функция полезности для поиска максимальной суммы между любыми

    // два листа. Эта функция вычисляет два значения:

    // 1) Максимальная сумма пути между двумя листами, которая хранится

    // в рез.

    // 2) Максимальная сумма пути от корня к листу, которая возвращается.

    // Если одна сторона корня пуста, то она возвращает INT_MIN

    public virtual int maxPathSumUtil(Node node, Res res)

    {

  

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

        if (node == null)

        {

            return 0;

        }

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

        {

            return node.data;

        }

  

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

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

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

        int ls = maxPathSumUtil(node.left, res);

        int rs = maxPathSumUtil(node.right, res);

  

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

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

        {

  

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

            res.val = Math.Max(res.val, ls + rs + node.data);

  

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

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

            return Math.Max(ls, rs) + node.data;

        }

  

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

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

        return (node.left == null) ? rs + node.data : ls + node.data;

    }

  

    // Основная функция, которая возвращает сумму максимума

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

    // использует maxPathSumUtil ()

    public virtual int maxPathSum(Node node)

    {

        Res res = new Res();

        res.val = int.MinValue;

        maxPathSumUtil(root, res);

        return res.val;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        BinaryTree.root = new Node(-15);

        BinaryTree.root.left = new Node(5);

        BinaryTree.root.right = new Node(6);

        BinaryTree.root.left.left = new Node(-8);

        BinaryTree.root.left.right = new Node(1);

        BinaryTree.root.left.left.left = new Node(2);

        BinaryTree.root.left.left.right = new Node(6);

        BinaryTree.root.right.left = new Node(3);

        BinaryTree.root.right.right = new Node(9);

        BinaryTree.root.right.right.right = new Node(0);

        BinaryTree.root.right.right.right.left = new Node(4);

        BinaryTree.root.right.right.right.right = new Node(-1);

        BinaryTree.root.right.right.right.right.left = new Node(10);

        Console.WriteLine("Max pathSum of the given binary tree is " + tree.maxPathSum(root));

    }

}

  

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


Выход:

Max pathSum of the given binary tree is 27.

Спасибо Saurabh Vats за предложенные исправления в оригинальном подходе.

Эта статья предоставлена Крипалом Гауравом . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

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

0.00 (0%) 0 votes