Рубрики

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

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

Примеры:

Input :       1
            /   \
           2      3
          / \    / \
         4   5  6   7
Output : 28
As all the tree elements are positive,
the largest subtree sum is equal to
sum of all tree elements.

Input :       1
            /    \
          -2      3
          / \    /  \
         4   5  -6   2
Output : 7
Subtree with largest sum is :  -2
                             /  \ 
                            4    5
Also, entire tree sum is also 7.

Рекомендуется: пожалуйста, попробуйте сначала свой подход к IDE, а затем посмотрите на решение.

Подход: сделать обход по порядку двоичного дерева. В каждом узле рекурсивно найдите значение левого поддерева и значение правого поддерева. Значение поддерева, укорененного в текущем узле, равно сумме значения текущего узла, суммы поддерева левого узла и суммы поддерева правого узла. Сравните текущую сумму поддерева с общей максимальной суммой поддерева.

Реализация :

C ++

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

using namespace std;

  
// Структура узла дерева.

struct Node {

    int key;

    Node *left, *right;

};

  
// Функция для создания нового узла дерева.

Node* newNode(int key)

{

    Node* temp = new Node;

    temp->key = key;

    temp->left = temp->right = NULL;

    return temp;

}

  
// Вспомогательная функция для поиска наибольшего
// сумма поддеревьев рекурсивно.

int findLargestSubtreeSumUtil(Node* root, int& ans)

{

    // Если текущий узел пуст

    // вернуть 0 в родительский узел.

    if (root == NULL)     

        return 0;

      

    // Сумма поддерева, укорененная в текущем узле.

    int currSum = root->key + 

      findLargestSubtreeSumUtil(root->left, ans)

      + findLargestSubtreeSumUtil(root->right, ans);

  

    // Обновить ответ, если текущее поддерево

    // сумма больше, чем ответ до сих пор.

    ans = max(ans, currSum);

  

    // Возвращаем текущую сумму поддерева в

    // его родительский узел.

    return currSum;

}

  
// Функция для поиска наибольшей суммы поддерева.

int findLargestSubtreeSum(Node* root)

{

    // Если дерево не существует,

    // тогда ответ 0.

    if (root == NULL)     

        return 0;

      

    // Переменная для хранения максимальной суммы поддерева.

    int ans = INT_MIN;

  

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

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

    findLargestSubtreeSumUtil(root, ans);

  

    return ans;

}

  
// Функция драйвера

int main()

{

    / *

               1

             / /

            / /

          -2 3

          / / / /

         / / / /

        4 5 -6 2

    * /

  

    Node* root = newNode(1);

    root->left = newNode(-2);

    root->right = newNode(3);

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

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

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

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

  

    cout << findLargestSubtreeSum(root);

    return 0;

}

Джава

// Java-программа для поиска крупнейших
// сумма поддерева в данном двоичном дереве.

import java.util.*; 

class GFG

{

  
// Структура узла дерева.

static class Node 

    int key; 

    Node left, right; 

  

static class INT

{

    int v;

    INT(int a)

    {

        v = a;

    }

}

  
// Функция для создания нового узла дерева.

static Node newNode(int key) 

    Node temp = new Node(); 

    temp.key = key; 

    temp.left = temp.right = null

    return temp; 

  
// Вспомогательная функция для поиска наибольшего
// сумма поддеревьев рекурсивно.

static int findLargestSubtreeSumUtil(Node root, 

                                     INT ans) 

    // Если текущий узел пуст

    // вернуть 0 в родительский узел.

    if (root == null)     

        return 0

      

    // поддерево сумма укорененная

    // на текущем узле.

    int currSum = root.key + 

    findLargestSubtreeSumUtil(root.left, ans) + 

    findLargestSubtreeSumUtil(root.right, ans); 

  

    // Обновить ответ, если текущее поддерево

    // сумма больше, чем ответ до сих пор.

    ans.v = Math.max(ans.v, currSum); 

  

    // Возвращаем текущее поддерево

    // сумма к его родительскому узлу.

    return currSum; 

  
// Функция для поиска
// самая большая сумма поддерева.

static int findLargestSubtreeSum(Node root) 

    // Если дерево не существует,

    // тогда ответ 0.

    if (root == null)     

        return 0

      

    // Переменная для хранения

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

    INT ans = new INT(-9999999); 

  

    // вызов рекурсивной функции

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

    findLargestSubtreeSumUtil(root, ans); 

  

    return ans.v; 

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

public static void main(String args[])

    / *

            1

            / /

            / /

        -2 3

        / / / /

        / / / /

        4 5 -6 2

    * /

  

    Node root = newNode(1); 

    root.left = newNode(-2); 

    root.right = newNode(3); 

    root.left.left = newNode(4); 

    root.left.right = newNode(5); 

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

    root.right.right = newNode(2); 

  

    System.out.println(findLargestSubtreeSum(root)); 


}

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

python3

# Python3 программа для поиска наибольшего поддерева
# сумма в данном двоичном дереве.

  
# Функция для создания нового узла дерева.

class newNode:

    def __init__(self, key):

        self.key = key 

        self.left = self.right = None

  
# Вспомогательная функция для поиска крупнейших
# сумма поддерева рекурсивно.

def findLargestSubtreeSumUtil(root, ans):

      

    # Если текущим узлом является None, то

    # вернуть 0 в родительский узел.

    if (root == None): 

        return 0

      

    # Сумма поддерева, укорененная в текущем узле.

    currSum = (root.key + 

               findLargestSubtreeSumUtil(root.left, ans) + 

               findLargestSubtreeSumUtil(root.right, ans)) 

  

    # Обновить ответ, если текущее поддерево

    # сумма больше, чем ответ до сих пор.

    ans[0] = max(ans[0], currSum) 

  

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

    # его родительский узел.

    return currSum

  
# Функция, чтобы найти наибольшую сумму поддерева.

def findLargestSubtreeSum(root):

      

    # Если дерево не существует,

    # тогда ответ 0.

    if (root == None):     

        return 0

      

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

    ans = [-999999999999]

  

    # Вызов рекурсивной функции для

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

    findLargestSubtreeSumUtil(root, ans) 

  

    return ans[0]

  
Код водителя

if __name__ == '__main__':

      

    #

    № 1

    # / /

    # / /

    № -2 3

    # / / / /

    # / / / /

    № 4 5 -6 2

    root = newNode(1

    root.left = newNode(-2

    root.right = newNode(3

    root.left.left = newNode(4

    root.left.right = newNode(5

    root.right.left = newNode(-6

    root.right.right = newNode(2

  

    print(findLargestSubtreeSum(root))

  
# Этот код предоставлен PranchalK

C #

using System;

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

  

public class GFG

{

  
// Структура узла дерева.

public class Node

{

    public int key;

    public Node left, right;

}

  

public class INT

{

    public int v;

    public INT(int a)

    {

        v = a;

    }

}

  
// Функция для создания нового узла дерева.

public static Node newNode(int key)

{

    Node temp = new Node();

    temp.key = key;

    temp.left = temp.right = null;

    return temp;

}

  
// Вспомогательная функция для поиска наибольшего
// сумма поддеревьев рекурсивно.

public static int findLargestSubtreeSumUtil(Node root, INT ans)

{

    // Если текущий узел пуст

    // вернуть 0 в родительский узел.

    if (root == null)

    {

        return 0;

    }

  

    // поддерево сумма укорененная

    // на текущем узле.

    int currSum = root.key + findLargestSubtreeSumUtil(root.left, ans)

                        + findLargestSubtreeSumUtil(root.right, ans);

  

    // Обновить ответ, если текущее поддерево

    // сумма больше, чем ответ до сих пор.

    ans.v = Math.Max(ans.v, currSum);

  

    // Возвращаем текущее поддерево

    // сумма к его родительскому узлу.

    return currSum;

}

  
// Функция для поиска
// самая большая сумма поддерева.

public static int findLargestSubtreeSum(Node root)

{

    // Если дерево не существует,

    // тогда ответ 0.

    if (root == null)

    {

        return 0;

    }

  

    // Переменная для хранения

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

    INT ans = new INT(-9999999);

  

    // вызов рекурсивной функции

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

    findLargestSubtreeSumUtil(root, ans);

  

    return ans.v;

}

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

public static void Main(string[] args)

{

    / *

            1

            / /

            / /

        -2 3

        / / / /

        / / / /

        4 5 -6 2

    * /

  

    Node root = newNode(1);

    root.left = newNode(-2);

    root.right = newNode(3);

    root.left.left = newNode(4);

    root.left.right = newNode(5);

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

    root.right.right = newNode(2);

  

    Console.WriteLine(findLargestSubtreeSum(root));

}
}

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

Выход:

7

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

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

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

0.00 (0%) 0 votes