Рубрики

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

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



In above binary tree chosen nodes are encircled 
and are not directly connected and their sum is
maximum possible.

Способ 1
Мы можем решить эту проблему, учитывая тот факт, что и узел, и его дочерние элементы не могут быть в сумме одновременно, поэтому, когда мы берем узел в нашу сумму, мы будем рекурсивно вызывать его внуков или когда мы не берем этот узел мы вызовем все его дочерние узлы и, наконец, выберем максимум из обоих этих результатов.
Легко видеть, что вышеуказанный подход может привести к решению одной и той же подзадачи много раз, например, на приведенной выше диаграмме узел 1 вызывает узлы 4 и 5, когда выбрано его значение, и узел 3 также вызывает их, когда его значение не выбрано, поэтому эти узлы обрабатывается более одного раза. Мы можем перестать решать эти узлы более одного раза, запоминая результат на всех узлах.
В приведенном ниже коде карта используется для запоминания результата, в котором хранится результат полного поддерева, укорененного в узле на карте, так что, если оно вызывается снова, значение не вычисляется снова, а сохраненное значение из карты возвращается напрямую.
Пожалуйста, смотрите код ниже для лучшего понимания.

C ++

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

using namespace std;

  
/ * Бинарная древовидная структура * /

struct node

{

    int data;

    struct node *left, *right;

};

  
/ * Служебная функция для создания нового узла двоичного дерева * /

struct node* newNode(int data)

{

    struct node *temp = new struct node;

    temp->data = data;

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

    return temp;

}

  
// Декларация методов

int sumOfGrandChildren(node* node);

int getMaxSum(node* node);

int getMaxSumUtil(node* node, map<struct node*, int>& mp);

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

int sumOfGrandChildren(node* node, map<struct node*, int>& mp)

{

    int sum = 0;

  

    // вызывать детей левого ребенка, только если он не равен NULL

    if (node->left)

        sum += getMaxSumUtil(node->left->left, mp) +

               getMaxSumUtil(node->left->right, mp);

  

    // вызывать детей правого ребенка, только если оно не NULL

    if (node->right)

        sum += getMaxSumUtil(node->right->left, mp) +

               getMaxSumUtil(node->right->right, mp);

  

    return sum;

}

  
// Служебный метод для возврата максимальной суммы с корнем в узле 'узел'

int getMaxSumUtil(node* node, map<struct node*, int>& mp)

{

    if (node == NULL)

        return 0;

  

    // Если узел уже обработан, возвращаем вычисленный

    // значение с карты

    if (mp.find(node) != mp.end())

        return mp[node];

  

    // принять текущее значение узла и вызвать всех внуков

    int incl = node->data + sumOfGrandChildren(node, mp);

  

    // не принимаем значение текущего узла и не вызываем все дочерние элементы

    int excl = getMaxSumUtil(node->left, mp) +

               getMaxSumUtil(node->right, mp);

  

    // выбираем максимум из обоих вышеуказанных вызовов и сохраняем их на карте

    mp[node] = max(incl, excl);

  

    return mp[node];

}

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

int getMaxSum(node* node)

{

    if (node == NULL)

        return 0;

    map<struct node*, int> mp;

    return getMaxSumUtil(node, mp);

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

  

    cout << getMaxSum(root) << endl;

    return 0;

}

Джава

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

import java.util.HashMap;

public class FindSumOfNotAdjacentNodes {

  

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

    // у grandChildrens узла 'узел'

    public static int sumOfGrandChildren(Node node, HashMap<Node,Integer> mp) 

    

        int sum = 0

        // вызывать детей левого ребенка, только если он не равен NULL

        if (node.left!=null

            sum += getMaxSumUtil(node.left.left, mp) + 

                   getMaxSumUtil(node.left.right, mp); 

    

        // вызывать детей правого ребенка, только если оно не NULL

        if (node.right!=null

            sum += getMaxSumUtil(node.right.left, mp) + 

                   getMaxSumUtil(node.right.right, mp); 

        return sum; 

    }

  

    // Служебный метод для возврата максимальной суммы с корнем в узле 'узел'

    public static int getMaxSumUtil(Node node, HashMap<Node,Integer> mp) 

    

        if (node == null

            return 0

    

        // Если узел уже обработан, возвращаем вычисленный

        // значение с карты

        if(mp.containsKey(node))

            return mp.get(node);

    

        // принять текущее значение узла и вызвать всех внуков

        int incl = node.data + sumOfGrandChildren(node, mp); 

    

        // не принимаем значение текущего узла и не вызываем все дочерние элементы

        int excl = getMaxSumUtil(node.left, mp) + 

                   getMaxSumUtil(node.right, mp); 

    

        // выбираем максимум из обоих вышеуказанных вызовов и сохраняем их на карте

        mp.put(node,Math.max(incl, excl)); 

    

        return mp.get(node); 

    

  

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

    // двоичного дерева при заданных ограничениях

    public static int getMaxSum(Node node) 

    

        if (node == null

            return 0

        HashMap<Node,Integer> mp=new HashMap<>();

        return getMaxSumUtil(node, mp); 

    }

  

    public static void main(String args[]) 

    {

        Node root = new Node(1); 

        root.left = new Node(2); 

        root.right = new Node(3); 

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

        root.right.right = new Node(5); 

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

        System.out.print(getMaxSum(root));

    }

}

  
/ * Бинарная древовидная структура * /

class Node 

    int data; 

    Node left, right; 

    Node(int data)

    {

        this.data=data;

        left=right=null;

    }

}; 
// Этот код предоставлен Гауравом Тивари

C #

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

using System;

using System.Collections.Generic; 

  

public class FindSumOfNotAdjacentNodes

{

  

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

    // возможно из корневых поддеревьев

    // у grandChildrens узла 'узел'

    public static int sumOfGrandChildren(Node node, 

                            Dictionary<Node,int> mp) 

    

        int sum = 0; 

          

        // вызов для детей левых

        // дочерний, только если он не равен NULL

        if (node.left != null

            sum += getMaxSumUtil(node.left.left, mp) + 

                getMaxSumUtil(node.left.right, mp); 

      

        // зовем детей правых

        // дочерний, только если он не равен NULL

        if (node.right != null

            sum += getMaxSumUtil(node.right.left, mp) + 

                getMaxSumUtil(node.right.right, mp); 

        return sum; 

    }

  

    // Служебный метод для возврата максимума

    // сумма с корнем в узле 'узел'

    public static int getMaxSumUtil(Node node,

                        Dictionary<Node,int> mp) 

    

        if (node == null

            return 0; 

      

        // Если узел уже обработан, то

        // возвращаем вычисленное значение с карты

        if(mp.ContainsKey(node))

            return mp[node];

      

        // принять текущее значение узла и

        // призываем всех внуков

        int incl = node.data + sumOfGrandChildren(node, mp); 

      

        // не принимаем текущее значение узла и

        // вызов для всех детей

        int excl = getMaxSumUtil(node.left, mp) + 

                getMaxSumUtil(node.right, mp); 

      

        // выбираем максимум из обоих выше

        // звоним и сохраняем это на карте

        mp.Add(node,Math.Max(incl, excl)); 

      

        return mp[node]; 

    

  

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

    // двоичного дерева при заданных ограничениях

    public static int getMaxSum(Node node) 

    

        if (node == null

            return 0; 

        Dictionary<Node,int> mp=new Dictionary<Node,int>();

        return getMaxSumUtil(node, mp); 

    }

  

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

    public static void Main(String []args) 

    {

        Node root = new Node(1); 

        root.left = new Node(2); 

        root.right = new Node(3); 

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

        root.right.right = new Node(5); 

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

        Console.Write(getMaxSum(root));

    }

}

  
/ * Бинарная древовидная структура * /

public class Node 

    public int data; 

    public Node left, right; 

    public Node(int data)

    {

        this.data=data;

        left=right=null;

    }

}; 

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


Выход:

11

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

C ++

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

using namespace std;

  

class Node

{

public:

    int data;

    Node* left, *right;

    Node(int data)

    {

        this->data = data;

        left = NULL;

        right = NULL;

    }

};

  

pair<int, int> maxSumHelper(Node *root)

{

    if (root==NULL)

    {

        pair<int, int> sum(0, 0);

        return sum;

    }

    pair<int, int> sum1 = maxSumHelper(root->left);

    pair<int, int> sum2 = maxSumHelper(root->right);

    pair<int, int> sum;

  

    // Этот узел включен (левый и правый потомки

    // не включены)

    sum.first = sum1.second + sum2.second + root->data;

  

    // Этот узел исключен (Левый или правый

    // ребенок включен)

    sum.second = max(sum1.first, sum1.second) +

                 max(sum2.first, sum2.second);

  

    return sum;

}

  

int maxSum(Node *root)

{

    pair<int, int> res = maxSumHelper(root);

    return max(res.first, res.second);

}

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

int main()

{

    Node *root= new Node(10);

    root->left= new Node(1);

    root->left->left= new Node(2);

    root->left->left->left= new Node(1);

    root->left->right= new Node(3);

    root->left->right->left= new Node(4);

    root->left->right->right= new Node(5);

    cout << maxSum(root);

    return 0;

}

Джава

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

public class FindSumOfNotAdjacentNodes {

  

    public static Pair maxSumHelper(Node root) 

    

        if (root==null

        

            Pair sum=new Pair(0, 0); 

            return sum; 

        

        Pair sum1 = maxSumHelper(root.left); 

        Pair sum2 = maxSumHelper(root.right); 

        Pair sum=new Pair(0,0); 

    

        // Этот узел включен (левый и правый потомки

        // не включены)

        sum.first = sum1.second + sum2.second + root.data; 

    

        // Этот узел исключен (Левый или правый

        // ребенок включен)

        sum.second = Math.max(sum1.first, sum1.second) + 

                     Math.max(sum2.first, sum2.second); 

    

        return sum; 

    

  

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

    // двоичного дерева при заданных ограничениях

    public static int maxSum(Node root)

    {

        Pair res=maxSumHelper(root); 

        return Math.max(res.first, res.second);

    }

  

    public static void main(String args[]) {

        Node root= new Node(10); 

        root.left= new Node(1); 

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

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

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

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

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

        System.out.print(maxSum(root)); 

    }

}

  
/ * Бинарная древовидная структура * /

class Node 

    int data; 

    Node left, right; 

    Node(int data)

    {

        this.data=data;

        left=right=null;

    }

}; 

  
/ * Парный класс * /

class Pair

{

    int first,second;

    Pair(int first,int second)

    {

        this.first=first;

        this.second=second;

    }

}
// Этот код предоставлен Гауравом Тивари

python3

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

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

  
"" "утилита, которая выделяет новый узел
с заданным ключом "" "

class newNode: 

  

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

    def __init__(self, key): 

        self.data = key

        self.left = None

        self.right = None

  

def maxSumHelper(root) :

  

    if (root == None): 

      

        sum = [0, 0

        return sum

      

    sum1 = maxSumHelper(root.left) 

    sum2 = maxSumHelper(root.right) 

    sum = [0, 0]

  

    # Этот узел включен (слева и справа

    # дети не включены)

    sum[0] = sum1[1] + sum2[1] + root.data 

  

    # Этот узел исключен (Левый или

    # правый ребенок включен)

    sum[1] = (max(sum1[0], sum1[1]) + 

              max(sum2[0], sum2[1])) 

  

    return sum

  

def maxSum(root) :

  

    res = maxSumHelper(root) 

    return max(res[0], res[1]) 

  
Код водителя

if __name__ == '__main__':

    root = newNode(10

    root.left = newNode(1

    root.left.left = newNode(2

    root.left.left.left = newNode(1

    root.left.right = newNode(3

    root.left.right.left = newNode(4

    root.left.right.right = newNode(5)

    print(maxSum(root))

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

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

using System;

  

public class FindSumOfNotAdjacentNodes 

  

    public static Pair maxSumHelper(Node root) 

    

        Pair sum;

        if (root == null

        

            sum=new Pair(0, 0); 

            return sum; 

        

        Pair sum1 = maxSumHelper(root.left); 

        Pair sum2 = maxSumHelper(root.right); 

        Pair sum3 = new Pair(0,0); 

      

        // Этот узел включен (слева и

        // правильные дети не включены)

        sum3.first = sum1.second + sum2.second + root.data; 

      

        // этот узел исключен (либо слева

        // или правый ребенок включен)

        sum3.second = Math.Max(sum1.first, sum1.second) + 

                    Math.Max(sum2.first, sum2.second); 

      

        return sum3; 

    

  

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

    // двоичного дерева при заданных ограничениях

    public static int maxSum(Node root) 

    

        Pair res=maxSumHelper(root); 

        return Math.Max(res.first, res.second); 

    

  

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

    public static void Main() 

    

        Node root = new Node(10); 

        root.left = new Node(1); 

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

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

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

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

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

        Console.Write(maxSum(root)); 

    

  
/ * Бинарная древовидная структура * /

public class Node 

    public int data; 

    public Node left, right; 

    public Node(int data) 

    

        this.data = data; 

        left = right = null

    

}; 

  
/ * Парный класс * /

public class Pair 

    public int first,second; 

    public Pair(int first,int second) 

    

        this.first = first; 

        this.second = second; 

    

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


Выход:

21

Временная сложность : O (n)

Спасибо Сурбхи Растоги за предложение этого метода.

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes