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

Опубликовано: 23 Января, 2022

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

 Вход : 
       7
      / 
     12 2
    /  
   11 13 5
  / / 
 2 1 38  

Выход: 44
BST с корнем под узлом 5 имеет максимальную сумму
       5
      / 
     1 38

Вход:
      5
     / 
    9 2
   / 
  6 3
 / 
8 7   

Выход: 8
Здесь каждый листовой узел представляет собой двоичное дерево поиска. 
также существует BST с суммой 5
     2
      
       3
Но у листового узла 8 максимальная сумма.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Approach: We traverse the tree in bottom-up manner. For every traversed node, we store the information of maximum and minimum of that subtree, a variable isBST to store if it is a BST, variable currmax to store the maximum sum of BST found till now, and a variable sum to store the sum of Left and Right subtree(which is also a BST) rooted under the current node.
Below is the implementation of the above approach: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Binary tree node
struct Node {
    struct Node* left;
    struct Node* right;
    int data;
 
    Node(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
 
// Information stored in every
// node during bottom up traversal
struct Info {
 
    // Max Value in the subtree
    int max;
 
    // Min value in the subtree
    int min;
 
    // If subtree is BST
    bool isBST;
 
    // Sum of the nodes of the sub-tree
    // rooted under the current node
    int sum;
 
    // Max sum of BST found till now
    int currmax;
};
 
// Returns information about subtree such as
// subtree with maximum sum which is also a BST
Info MaxSumBSTUtil(struct Node* root, int& maxsum)
{
    // Base case
    if (root == NULL)
        return { INT_MIN, INT_MAX, true, 0, 0 };
 
    // If current node is a leaf node then
    // return from the function and store
    // information about the leaf node
    if (root->left == NULL && root->right == NULL) {
        maxsum = max(maxsum, root->data);
        return { root->data, root->data, true, root->data, maxsum };
    }
 
    // Store information about the left subtree
    Info L = MaxSumBSTUtil(root->left, maxsum);
 
    // Store information about the right subtree
    Info R = MaxSumBSTUtil(root->right, maxsum);
 
    Info BST;
 
    // If the subtree rooted under the current node
    // is a BST
    if (L.isBST && R.isBST && L.max < root->data && R.min > root->data) {
 
        BST.max = max(root->data, max(L.max, R.max));
        BST.min = min(root->data, min(L.min, R.min));
 
        maxsum = max(maxsum, R.sum + root->data + L.sum);
        BST.sum = R.sum + root->data + L.sum;
 
        // Update the current maximum sum
        BST.currmax = maxsum;
 
        BST.isBST = true;
        return BST;
    }
 
    // If the whole tree is not a BST then
    // update the current maximum sum
    BST.isBST = false;
    BST.currmax = maxsum;
    BST.sum = R.sum + root->data + L.sum;
 
    return BST;
}
 
// Function to return the maximum
// sum subtree which is also a BST
int MaxSumBST(struct Node* root)
{
    int maxsum = INT_MIN;
    return MaxSumBSTUtil(root, maxsum).currmax;
}
 
// Driver code
int main()
{
    struct Node* root = new Node(5);
    root->left = new Node(14);
    root->right = new Node(3);
    root->left->left = new Node(6);
    root->right->right = new Node(7);
    root->left->left->left = new Node(9);
    root->left->left->right = new Node(1);
 
    cout << MaxSumBST(root);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
     
// Binary tree node
static class Node
{
    Node left;
    Node right;
    int data;
 
    Node(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
};
 
// Information stored in every
// node during bottom up traversal
static class Info
{
 
    // Max Value in the subtree
    int max;
 
    // Min value in the subtree
    int min;
 
    // If subtree is BST
    boolean isBST;
 
    // Sum of the nodes of the sub-tree
    // rooted under the current node
    int sum;
 
    // Max sum of BST found till now
    int currmax;
     
    Info(int m,int mi,boolean is,int su,int cur)
    {
        max = m;
        min = mi;
        isBST = is;
        sum = su;
        currmax = cur;
    }
    Info(){}
};
 
static class INT
{
    int a;
}
 
// Returns information about subtree such as
// subtree with the maximum sum which is also a BST
static Info MaxSumBSTUtil( Node root, INT maxsum)
{
    // Base case
    if (root == null)
        return new Info( Integer.MIN_VALUE,
                        Integer.MAX_VALUE, true, 0, 0 );
 
    // If current node is a leaf node then
    // return from the function and store
    // information about the leaf node
    if (root.left == null && root.right == null)
    {
        maxsum.a = Math.max(maxsum.a, root.data);
        return new Info( root.data, root.data,
                        true, root.data, maxsum.a );
    }
 
    // Store information about the left subtree
    Info L = MaxSumBSTUtil(root.left, maxsum);
 
    // Store information about the right subtree
    Info R = MaxSumBSTUtil(root.right, maxsum);
 
    Info BST=new Info();
 
    // If the subtree rooted under the current node
    // is a BST
    if (L.isBST && R.isBST && L.max < root.data &&
                               R.min > root.data)
    {
 
        BST.max = Math.max(root.data, Math.max(L.max, R.max));
        BST.min = Math.min(root.data, Math.min(L.min, R.min));
 
        maxsum.a = Math.max(maxsum.a, R.sum + root.data + L.sum);
        BST.sum = R.sum + root.data + L.sum;
 
        // Update the current maximum sum
        BST.currmax = maxsum.a;
 
        BST.isBST = true;
        return BST;
    }
 
    // If the whole tree is not a BST then
    // update the current maximum sum
    BST.isBST = false;
    BST.currmax = maxsum.a;
    BST.sum = R.sum + root.data + L.sum;
 
    return BST;
}
 
// Function to return the maximum
// sum subtree which is also a BST
static int MaxSumBST( Node root)
{
    INT maxsum = new INT();
    maxsum.a = Integer.MIN_VALUE;
    return MaxSumBSTUtil(root, maxsum).currmax;
}
 
// Driver code
public static void main(String args[])
{
    Node root = new Node(5);
    root.left = new Node(14);
    root.right = new Node(3);
    root.left.left = new Node(6);
    root.right.right = new Node(7);
    root.left.left.left = new Node(9);
    root.left.left.right = new Node(1);
 
    System.out.println( MaxSumBST(root));
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation of
# the above approach
from sys import maxsize as INT_MAX
INT_MIN = -INT_MAX
 
# Binary tree node
class Node:
   
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Information stored in every
# node during bottom up traversal
class Info:
   
    def __init__(self, _max, _min,
                 isBST, _sum, currmax):
       
        # Max Value in the subtree
        self.max = _max
 
        # Min value in the subtree
        self.min = _min
 
        # If subtree is BST
        self.isBST = isBST
 
        # Sum of the nodes of the sub-tree
        # rooted under the current node
        self.sum = _sum
 
        # Max sum of BST found till now
        self.currmax = currmax
 
# Returns information about
# subtree such as subtree
# with maximum sum which
# is also a BST
def MaxSumBSTUtil(root: Node) -> Info:
    global maxsum
 
    # Base case
    if (root is None):
        return Info(INT_MIN, INT_MAX,
                    True, 0, 0)
 
    # If current node is a
    # leaf node then return
    # from the function and store
    # information about the leaf node
    if (root.left is None and
        root.right is None):
        maxsum = max(maxsum,
                     root.data)
        return Info(root.data, root.data,
                    True, root.data, maxsum)
 
    # Store information about
    # the left subtree
    L = MaxSumBSTUtil(root.left)
 
    # Store information about
    # the right subtree
    R = MaxSumBSTUtil(root.right)
 
    BST = Info
 
    # If the subtree rooted under
    # the current node is a BST
    if (L.isBST and R.isBST and
        L.max < root.data and
        R.min > root.data):
 
        BST.max = max(root.data,
                  max(L.max, R.max))
        BST.min = min(root.data,
                  min(L.min, R.min))
 
        maxsum = max(maxsum, R.sum +
                     root.data + L.sum)
        BST.sum = R.sum + root.data + L.sum
 
        # Update the current maximum sum
        BST.currmax = maxsum
 
        BST.isBST = True
        return BST
 
    # If the whole tree is not
    # a BST then update the
    # current maximum sum
    BST.isBST = False
    BST.currmax = maxsum
    BST.sum = R.sum + root.data + L.sum
 
    return BST
 
# Function to return the maximum
# sum subtree which is also a BST
def MaxSumBST(root: Node) -> int:
    global maxsum
    return MaxSumBSTUtil(root).currmax
 
# Driver code
if __name__ == "__main__":
 
    root = Node(5)
    root.left = Node(14)
    root.right = Node(3)
    root.left.left = Node(6)
    root.right.right = Node(7)
    root.left.left.left = Node(9)
    root.left.left.right = Node(1)
 
    maxsum = INT_MIN
    print(MaxSumBST(root))
 
# This code is contributed by sanjeev2552

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
// Binary tree node
public class Node
{
    public Node left;
    public Node right;
    public int data;
 
    public Node(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
};
 
// Information stored in every
// node during bottom up traversal
public class Info
{
 
    // Max Value in the subtree
    public int max;
 
    // Min value in the subtree
    public int min;
 
    // If subtree is BST
    public bool isBST;
 
    // Sum of the nodes of the sub-tree
    // rooted under the current node
    public int sum;
 
    // Max sum of BST found till now
    public int currmax;
     
 
Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022