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

31.12.2019Деревья

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

Пример:

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