Рубрики

Крупнейший BST в двоичном дереве | Набор 2

Для заданного двоичного дерева напишите функцию, которая возвращает размер наибольшего поддерева, которое также является двоичным деревом поиска (BST). Если полное двоичное дерево имеет тип BST, вернуть размер всего дерева.

Примеры:

Input: 
      5
    /  \
   2    4
 /  \
1    3

Output: 3 
The following subtree is the 
maximum size BST subtree 
   2  
 /  \
1    3


Input: 
       50
     /    \
  30       60
 /  \     /  \ 
5   20   45    70
              /  \
            65    80
Output: 5
The following subtree is the
maximum size BST subtree 
      60
     /  \ 
   45    70
        /  \
      65    80

Рекомендуется: пожалуйста, решите это на “ Прежде чем перейти к решению.

Мы обсудили два метода в посте ниже.
Найти наибольшее поддерево BST в данном двоичном дереве | Комплект 1

В этом посте обсуждается другое решение O (n). Это решение проще, чем решения, рассмотренные выше, и работает за O (n) времени.

Идея основана на методе 3 проверки, является ли двоичное дерево статьей BST .

Дерево является BST, если для каждого узла x верно следующее.

  1. Наибольшее значение в левом поддереве (x) меньше значения x.
  2. Наименьшее значение в правом поддереве (x) больше значения x.

Мы проходим дерево снизу вверх. Для каждого пройденного узла мы возвращаем максимальное и минимальное значения в поддереве с корнем. Если какой-либо узел следует вышеуказанным свойствам и размеру

C ++

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

using namespace std;

  
/ * Узел двоичного дерева содержит данные,
указатель на левого ребенка и
указатель на правого ребенка * /

struct Node

{

    int data;

    struct Node* left;

    struct Node* right;

};

  
/ * Вспомогательная функция, которая выделяет новый
узел с заданными данными и NULL слева
и правильные указатели. * /

struct Node* newNode(int data)

{

    struct Node* node = new Node;

    node->data = data;

    node->left = node->right = NULL;

  

    return(node);

}

  
// Информация, которую должен возвращать каждый
// узел в обходе снизу вверх.

struct Info

{

    int sz; // Размер поддерева

    int max; // Минимальное значение в поддереве

    int min; // Максимальное значение в поддереве

    int ans; // Размер самого большого BST, который

    // поддерево текущего узла

    bool isBST; // Если поддерево BST

};

  
// Возвращает информацию о поддереве.
// Информация также включает в себя размер наибольшего
// поддерево, которое является BST.
Info largestBSTBT(Node* root)
{

    // Базовые случаи: когда дерево пустое или имеет

    // один ребенок.

    if (root == NULL)

        return {0, INT_MIN, INT_MAX, 0, true};

    if (root->left == NULL && root->right == NULL)

        return {1, root->data, root->data, 1, true};

  

    // Повторение для левого поддерева и правого поддерева

    Info l = largestBSTBT(root->left);

    Info r = largestBSTBT(root->right);

  

    // Создаем возвращаемую переменную и инициализируем ее

    // размер.

    Info ret;

    ret.sz = (1 + l.sz + r.sz);

  

    // Если все дерево с корнем под текущим корнем

    // BST.

    if (l.isBST && r.isBST && l.max < root->data &&

            r.min > root->data)

    {

        ret.min = min(l.min, min(r.min, root->data));

        ret.max = max(r.max, max(l.max, root->data));

  

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

        // текущий 'root'

        ret.ans = ret.sz;

        ret.isBST = true;

  

        return ret;

    }

  

    // Если все дерево не BST, вернуть максимум

    // левого и правого поддеревьев

    ret.ans = max(l.ans, r.ans);

    ret.isBST = false;

  

    return ret;

}

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

int main()

{

    / * Давайте построим следующее дерево

        60

       / /

      65 70

     /

    50 *

  

    struct Node *root = newNode(60);

    root->left = newNode(65);

    root->right = newNode(70);

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

    printf(" Size of the largest BST is %d\n",

           largestBSTBT(root).ans);

    return 0;

}

  
// Этот код предоставлен Vivek Garg в
// комментируем нижний набор 1.
// www.geeksforgeeks.org/find-the-largest-subtree-in-a-tree-that-is-also-a-bst/

python3

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

  

INT_MIN = -2147483648

INT_MAX = 2147483647

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

class newNode: 

  

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

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

  
# Возвращает информацию о поддереве.
# Информация также включает в себя размер наибольшего
# поддерево, которое является BST

def largestBSTBT(root):

      
# Базовые случаи: когда дерево пустое или имеет

    # один ребенок.

    if (root == None):

        return 0, INT_MIN, INT_MAX, 0, True

    if (root.left == None and root.right == None) :

        return 1, root.data, root.data, 1, True

  

    # Recur для левого поддерева и правого поддерева

    l = largestBSTBT(root.left) 

    r = largestBSTBT(root.right) 

  

    # Создайте возвращаемую переменную и инициализируйте ее

    # размер.

    ret = [0, 0, 0, 0, 0

    ret[0] = (1 + l[0] + r[0]) 

  

    # Если все дерево с корнем под текущим корнем

    # BST.

    if (l[4] and r[4] and l[1] < 

        root.data and r[2] > root.data) :

      

        ret[2] = min(l[2], min(r[2], root.data)) 

        ret[1] = max(r[1], max(l[1], root.data)) 

  

        # Обновить ответ для дерева с корнем под

        # текущий 'root'

        ret[3] = ret[0

        ret[4] = True

  

        return ret 

      

  

    # Если все дерево не BST, верните максимум

    Количество левых и правых поддеревьев

    ret[3] = max(l[3], r[3]) 

    ret[4] = False

  

    return ret

  
Код водителя

if __name__ == '__main__'

      

    "" "Давайте построим следующее дерево

        60

        / /

        65 70

    /

    50 "" "

    root = newNode(60

    root.left = newNode(65

    root.right = newNode(70

    root.left.left = newNode(50)

    print("Size of the largest BST is",

                    largestBSTBT(root)[3]) 

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

Выход:

Size of largest BST is 2

Сложность времени: O (n)

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

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

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

Крупнейший BST в двоичном дереве | Набор 2

0.00 (0%) 0 votes