Рубрики

Максимальная сумма пути в двоичном дереве

По заданному бинарному дереву найдите максимальную сумму пути. Путь может начинаться и заканчиваться в любом узле дерева.

Пример:

Input: Root of below tree
       1
      / \
     2   3
Output: 6

See below diagram for another example.
1+2+3

Для каждого узла может быть четыре пути прохождения максимального пути через узел:
1. Узел только
2. Максимальный путь через левого ребенка + узел
3. Максимальный путь через Right Child + Node
4. Максимальный путь через левого ребенка + узел + Максимальный путь через правого ребенка

Идея состоит в том, чтобы отслеживать четыре пути и в конце выбрать максимальный. Важно отметить, что корень каждого поддерева должен возвращать максимальную сумму пути, чтобы в нем участвовал не более одного дочернего элемента root. Это необходимо для вызова родительской функции. В приведенном ниже коде эта сумма сохраняется в max_single и возвращается рекурсивной функцией.

C ++

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

using namespace std;

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

struct Node

{

    int data;

    struct Node* left, *right;

};

  
// Сервисная функция для выделения нового узла

struct Node* newNode(int data)

{

    struct Node* newNode = new Node;

    newNode->data = data;

    newNode->left = newNode->right = NULL;

    return (newNode);

}

  
// Эта функция возвращает общую максимальную сумму пути в 'res'
// И возвращает максимальную сумму пути, проходящую через корень.

int findMaxUtil(Node* root, int &res)

{

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

    if (root == NULL)

        return 0;

  

    // l и r сохраняют максимальную сумму пути, проходящую влево и

    // правый потомок root соответственно

    int l = findMaxUtil(root->left,res);

    int r = findMaxUtil(root->right,res);

  

    // Максимальный путь для родительского вызова root. Этот путь должен

    // включить не более одного потомка root

    int max_single = max(max(l, r) + root->data, root->data);

  

    // Max Top представляет сумму, когда узел под

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

    // предки root находятся в пути max sum

    int max_top = max(max_single, l + r + root->data);

  

    res = max(res, max_top); // Сохраняем максимальный результат.

  

    return max_single;

}

  
// Возвращает максимальную сумму пути в дереве с заданным корнем

int findMaxSum(Node *root)

{

    // Инициализировать результат

    int res = INT_MIN;

  

    // Вычисляем и возвращаем результат

    findMaxUtil(root, res);

    return res;

}

  
// Драйвер программы

int main(void)

{

    struct Node *root = newNode(10);

    root->left        = newNode(2);

    root->right       = newNode(10);

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

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

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

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

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

    cout << "Max path sum is " << findMaxSum(root);

    return 0;

}

Джава

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

  
/ * Класс, содержащий левого и правого потомка текущего

 значение узла и ключа * /

class Node {

  

    int data;

    Node left, right;

  

    public Node(int item) {

        data = item;

        left = right = null;

    }

}

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

class Res {

    public int val;

}

  

class BinaryTree {

  

    // Корень бинарного дерева

    Node root;

  

    // Эта функция возвращает общую максимальную сумму пути в 'res'

    // И возвращает максимальную сумму пути, проходящую через корень.

    int findMaxUtil(Node node, Res res)

    {

  

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

        if (node == null)

            return 0;

  

        // l и r сохраняют максимальную сумму пути, проходящую влево и

        // правый потомок root соответственно

        int l = findMaxUtil(node.left, res);

        int r = findMaxUtil(node.right, res);

  

        // Максимальный путь для родительского вызова root. Этот путь должен

        // включить не более одного потомка root

        int max_single = Math.max(Math.max(l, r) + node.data,

                                  node.data);

  

  

        // Max Top представляет сумму, когда узел под

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

        // предки root находятся в пути max sum

        int max_top = Math.max(max_single, l + r + node.data);

  

        // Сохраняем максимальный результат.

        res.val = Math.max(res.val, max_top);

  

        return max_single;

    }

  

    int findMaxSum() {

        return findMaxSum(root);

    }

  

    // Возвращает максимальную сумму пути в дереве с заданным корнем

    int findMaxSum(Node node) {

  

        // Инициализировать результат

        // int res2 = Integer.MIN_VALUE;

        Res res = new Res();

        res.val = Integer.MIN_VALUE;

  

        // Вычисляем и возвращаем результат

        findMaxUtil(node, res);

        return res.val;

    }

  

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

    public static void main(String args[]) {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

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

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

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

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

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

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

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

        System.out.println("maximum path sum is : " +

                            tree.findMaxSum());

    }

}

питон

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

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

class Node:

      

    # Contructor для создания нового узла

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Эта функция возвращает общую максимальную сумму пути в 'res'
# И возвращает максимальную сумму пути, проходящую через корень

def findMaxUtil(root):

      

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

    if root is None:

        return 0 

  

    # l и r хранят максимальную сумму пути, проходящую через левое

    # и правый потомок корня соответственно

    l = findMaxUtil(root.left)

    r = findMaxUtil(root.right)

      

    # Максимальный путь для родительского вызова root. Этот путь

    # должен включать не более одного потомка root

    max_single = max(max(l, r) + root.data, root.data)

      

    # Max top представляет сумму, когда узел под

    # рассмотрение является корнем пути maxSum и

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

    max_top = max(max_single, l+r+ root.data)

  

    # Статическая переменная для хранения изменений

    # Хранить максимальный результат

    findMaxUtil.res = max(findMaxUtil.res, max_top) 

  

    return max_single

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

def findMaxSum(root):

      

    # Инициализировать результат

    findMaxUtil.res = float("-inf")

      

    # Вычислить и вернуть результат

    findMaxUtil(root)

    return findMaxUtil.res

  
# Драйверная программа

root = Node(10)

root.left = Node(2)

root.right   = Node(10);

root.left.left  = Node(20);

root.left.right = Node(1);

root.right.right = Node(-25);

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

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

print "Max path sum is " ,findMaxSum(root);

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

C #

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

using System;

  
/ * Класс, содержащий слева и
правый ребенок текущего
значение узла и ключа * /

public class Node 

{

  

    public int data;

    public Node left, right;

  

    public Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

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

class Res 

{

    public int val;

}

  

public class BinaryTree 

{

  

    // Корень бинарного дерева

    Node root;

  

    // Эта функция возвращает в целом

    // максимальная сумма пути в 'res' А

    // возвращает максимальную сумму пути, проходящую через корень.

    int findMaxUtil(Node node, Res res)

    {

  

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

        if (node == null)

            return 0;

  

        // l и r сохраняют максимальный путь

        // сумма, проходящая слева и

        // правый потомок root соответственно

        int l = findMaxUtil(node.left, res);

        int r = findMaxUtil(node.right, res);

  

        // Максимальный путь для родительского вызова root.

        // Этот путь должен включать

        // не более одного потомка root

        int max_single = Math.Max(Math.Max(l, r) + 

                            node.data, node.data);

  

  

        // Max Top представляет сумму

        // когда узел под

        // рассмотрение является корнем

        // максимального пути и нет

        // есть предки root

        // в пути максимальной суммы

        int max_top = Math.Max(max_single,

                        l + r + node.data);

  

        // Сохраняем максимальный результат.

        res.val = Math.Max(res.val, max_top);

  

        return max_single;

    }

  

    int findMaxSum() 

    {

        return findMaxSum(root);

    }

  

    // Возвращает максимальный путь

    // сумма в дереве с заданным корнем

    int findMaxSum(Node node)

    {

  

        // Инициализировать результат

        // int res2 = int.MinValue;

        Res res = new Res();

        res.val = int.MinValue;

  

        // Вычисляем и возвращаем результат

        findMaxUtil(node, res);

        return res.val;

    }

  

    / * Код водителя * /

    public static void Main(String []args) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

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

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

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

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

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

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

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

        Console.WriteLine("maximum path sum is : " +

                            tree.findMaxSum());

    }

}

  
// Этот код предоставлен Rajput-Ji.


Выход:

Max path sum is 42

Сложность времени: O (n), где n — количество узлов в двоичном дереве.

Эта статья предоставлена Анмолом Варшни (профиль FB: https://www.facebook.com/anmolvarshney695 ). Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Максимальная сумма пути в двоичном дереве

0.00 (0%) 0 votes