Рубрики

Найти наибольшее поддерево BST в данном двоичном дереве | Комплект 1

Для заданного двоичного дерева напишите функцию, которая возвращает размер наибольшего поддерева, которое также является двоичным деревом поиска (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

Способ 1 (простой, но неэффективный)
Начните с корня и выполните обход дерева по порядку. Для каждого узла N проверьте, является ли поддерево с корнем из N BST или нет. Если BST, то вернуть размер поддерева с корнем из N. Иначе, повторить левое и правое поддеревья и вернуть максимум значений, возвращенных левым и правым поддеревьями.

/ *

  См. Https://www.geeksforgeeks.org/write-ac-program-to-calculate-size-of-a-tree/amp/ для реализации size ()

  

  См. Метод 3 https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/amp/ для

  реализация isBST ()

  

  max () возвращает максимум двух целых

* /   

int largestBST(struct node *root)

{

   if (isBST(root))

     return size(root); 

   else

    return max(largestBST(root->left), largestBST(root->right));

}

Сложность времени: наихудшая временная сложность этого метода будет O (n ^ 2). Рассмотрим перекошенное дерево для анализа наихудшего случая.

Метод 2 (хитрый и эффективный)
В методе 1 мы просматриваем дерево сверху вниз и выполняем тест BST для каждого узла. Если мы пройдем дерево снизу вверх, то сможем передать информацию о поддеревьях родителю. Переданная информация может использоваться родителем для выполнения теста BST (для родительского узла) только в постоянное время (или O (1) время). Левое поддерево должно сказать родителю, является ли это BST или нет, и также должно передать в нем максимальное значение. Так что мы можем сравнить максимальное значение с данными родителя, чтобы проверить свойство BST. Точно так же правильное поддерево должно передать минимальное значение вверх по дереву. Поддеревам необходимо передать следующую информацию вверх по дереву для нахождения наибольшего BST.
1) Независимо от того, является ли само поддерево BST или нет (в следующем коде для этой цели используется is_bst_ref)
2) Если поддерево осталось поддеревом своего родителя, то в нем максимальное значение. И если это правильное поддерево, то минимальное значение в нем.
3) Размер этого поддерева, если это поддерево — BST (В следующем коде для этой цели используется возвращаемое значение mostBSTtil ())

max_ref используется для передачи максимального значения вверх по дереву, а min_ptr используется для передачи минимального значения вверх по дереву.

C ++

// C ++ программа вышеуказанного подхода
#include<bits/stdc++.h> 
#include<iostream>

using namespace std; 

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

class node 

    public:

    int data; 

    node* left; 

    node* right; 

      

    / * Конструктор, который выделяет

    новый узел с заданными данными

    и NULL левый и правый указатели. * /

    node(int data)

    {

        this->data = data;

        this->left = NULL;

        this->right = NULL;

          

    }

}; 

  

  

int largestBSTUtil(node* node, int *min_ref, int *max_ref, 

                    int *max_size_ref, bool *is_bst_ref); 

  
/ * Возвращает размер самого большого BST
поддерево в бинарном дереве
(эффективная версия). * /

int largestBST(node* node) 

    // Устанавливаем начальные значения для

    // вызов самого крупногоBSTUtil ()

    int min = INT_MAX; // Для минимального значения в правом поддереве

    int max = INT_MIN; // Для максимального значения в левом поддереве

      

    int max_size = 0; // Для размера самого большого BST

    bool is_bst = 0; 

      

    largestBSTUtil(node, &min, &max, 

                    &max_size, &is_bst); 

      

    return max_size; 

  
/ * крупнейшийBSTUtil () обновляет * max_size_ref
для размера самого большого поддерева BST.
Кроме того, если дерево с корнем
непустой и BST, затем возвращает размер
дерева. В противном случае возвращает 0. * /

int largestBSTUtil(node* node, int *min_ref, int *max_ref, 

                    int *max_size_ref, bool *is_bst_ref) 

  

    /* Базовый вариант */

    if (node == NULL) 

    

        *is_bst_ref = 1; // Пустое дерево BST

        return 0; // Размер BST равен 0

    

      

    int min = INT_MAX; 

      

    / * Переменная флага для свойства левого поддерева

        то есть, max (root-> left) <root-> data * /

    bool left_flag = false

      

    / * Переменная флага для свойства правого поддерева

        т.е. min (root-> right)> root-> data * /

    bool right_flag = false

      

    int ls, rs; // Для хранения размеров левого и правого поддеревьев

      

    / * Следующие задачи выполняются

    рекурсивный вызов для левого поддерева

        а) Получить максимальное значение слева

        поддерево (хранится в * max_ref)

        б) Проверьте, является ли левое поддерево

        BST или нет (хранится в * is_bst_ref)

        в) Получить размер максимального размера BST

        в левом поддереве (обновления * max_size) * /

    *max_ref = INT_MIN; 

    ls = largestBSTUtil(node->left, min_ref, max_ref,

                        max_size_ref, is_bst_ref); 

    if (*is_bst_ref == 1 && node->data > *max_ref) 

        left_flag = true

      

    / * Перед обновлением * min_ref, сохраните мин.

    значение в левом поддереве. Так что у нас есть

    правильное минимальное значение для этого поддерева * /

    min = *min_ref; 

      

    / * Следующий рекурсивный вызов

    делает подобное (похоже на левое поддерево)

    задание для правого поддерева * /

    *min_ref = INT_MAX; 

    rs = largestBSTUtil(node->right, min_ref, 

                        max_ref, max_size_ref, is_bst_ref); 

    if (*is_bst_ref == 1 && node->data < *min_ref) 

        right_flag = true

      

    // Обновляем минимальное и максимальное значения для

    // родительские рекурсивные вызовы

    if (min < *min_ref) 

        *min_ref = min; 

    if (node->data < *min_ref) // Для листовых узлов

        *min_ref = node->data; 

    if (node->data > *max_ref) 

        *max_ref = node->data; 

      

    / * Если левое и правое поддеревья имеют BST.

    И свойства левого и правого поддерева держатся

    для этого узла, то это дерево BST.

    Так что верните размер этого дерева * /

    if(left_flag && right_flag) 

    

        if (ls + rs + 1 > *max_size_ref) 

            *max_size_ref = ls + rs + 1; 

        return ls + rs + 1; 

    

    else

    

        // Поскольку это поддерево не BST,

        // устанавливаем флаг is_bst для родительских вызовов

        *is_bst_ref = 0; 

        return 0; 

    

  
/ * Код водителя * /

int main() 

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

            50

        / /

        10 60

        / / / /

    5 20 55 70

                ///

            45 65 80

    * /

      

    node *root = new node(50); 

    root->left = new node(10); 

    root->right = new node(60); 

    root->left->left = new node(5); 

    root->left->right = new node(20); 

    root->right->left = new node(55); 

    root->right->left->left = new node(45); 

    root->right->right = new node(70); 

    root->right->right->left = new node(65); 

    root->right->right->right = new node(80); 

      

    / * Полное дерево не BST

    как 45 в правильном поддереве 50.

    Следующее поддерево является самым большим BST

            60

        / /

        55 70

    ///

    45 65 80

    * /

    cout<<" Size of the largest BST is "<< largestBST(root); 

  

    return 0; 

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

С

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

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

   и указатель на правого ребенка * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

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

   данные даны и NULL левый и правый указатели. * /

struct node* newNode(int data)

{

  struct node* node = (struct node*)

                      malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

  

  return(node);

}

  

int largestBSTUtil(struct node* node, int *min_ref, int *max_ref,

                             int *max_size_ref, bool *is_bst_ref);

  
/ * Возвращает размер самого большого поддерева BST в двоичном дереве

  (эффективная версия). * /

int largestBST(struct node* node)

{

  // Устанавливаем начальные значения для вызова mostBSTUtil ()

  int min = INT_MAX;  // Для минимального значения в правом поддереве

  int max = INT_MIN;  // Для максимального значения в левом поддереве

  

  int max_size = 0;  // Для размера самого большого BST

  bool is_bst = 0;

  

  largestBSTUtil(node, &min, &max, &max_size, &is_bst);

  

  return max_size;

}

  
/ *gestBSTUtil () обновляет * max_size_ref для размера самого большого BST

   поддерево. Кроме того, если дерево с корнем не является пустым и BST,

   затем возвращает размер дерева. В противном случае возвращает 0. * /

int largestBSTUtil(struct node* node, int *min_ref, int *max_ref,

                            int *max_size_ref, bool *is_bst_ref)

{

  

  /* Базовый вариант */

  if (node == NULL)

  {

     *is_bst_ref = 1; // Пустое дерево BST

     return 0;    // Размер BST равен 0

  }

  

  int min = INT_MAX;

  

  / * Переменная флага для свойства левого поддерева

     то есть, max (root-> left) <root-> data * /

  bool left_flag = false;

  

  / * Переменная флага для свойства правого поддерева

     т.е. min (root-> right)> root-> data * /

  bool right_flag = false;

  

  int ls, rs; // Для хранения размеров левого и правого поддеревьев

  

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

    а) Получить максимальное значение в левом поддереве (хранится в * max_ref)

    б) Проверьте, является ли левое поддерево BST или нет (хранится в * is_bst_ref)

    в) Получить размер максимального размера BST в левом поддереве (обновления * max_size) * /

  *max_ref = INT_MIN;

  ls = largestBSTUtil(node->left, min_ref, max_ref, max_size_ref, is_bst_ref);

  if (*is_bst_ref == 1 && node->data > *max_ref)

     left_flag = true;

  

  / * Перед обновлением * min_ref сохраните значение min в левом поддереве. Так что мы

     иметь правильное минимальное значение для этого поддерева * /

  min = *min_ref;

  

  / * Следующий рекурсивный вызов делает подобное (аналогично левому поддереву)

    задание для правого поддерева * /

  *min_ref =  INT_MAX;

  rs = largestBSTUtil(node->right, min_ref, max_ref, max_size_ref, is_bst_ref);

  if (*is_bst_ref == 1 && node->data < *min_ref)

     right_flag = true;

  

  // Обновляем минимальное и максимальное значения для родительских рекурсивных вызовов

  if (min < *min_ref)

     *min_ref = min;

  if (node->data < *min_ref) // Для листовых узлов

     *min_ref = node->data;

  if (node->data > *max_ref)

     *max_ref = node->data;

  

  / * Если левое и правое поддеревья имеют BST. И левый и правый

     для этого узла сохраняются свойства поддерева, тогда это дерево BST.

     Так что верните размер этого дерева * /

  if(left_flag && right_flag)

  {

     if (ls + rs + 1 > *max_size_ref)

         *max_size_ref = ls + rs + 1;

     return ls + rs + 1;

  }

  else

  {

    // Поскольку это поддерево не BST, установить флаг is_bst для родительских вызовов

     *is_bst_ref = 0; 

     return 0;

  }

}

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

int main()

{

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

          50

       / /

     10 60

    / / / /

   5 20 55 70

            ///

          45 65 80

  * /

  

  struct node *root = newNode(50);

  root->left        = newNode(10);

  root->right       = newNode(60);

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

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

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

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

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

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

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

  

  / * Полное дерево не BST, поскольку 45 находится в правом поддереве 50.

     Следующее поддерево является самым большим BST

        60

      / /

    55 70

   ///

 45 65 80

  * /

  printf(" Size of the largest BST is %d", largestBST(root));

  

  getchar();

  return 0;

}

Джава

// Java-программа для поиска наибольшего поддерева BST в заданном двоичном дереве

  

class Node {

  

    int data;

    Node left, right;

  

    Node(int d) {

        data = d;

        left = right = null;

    }

}

  

class Value {

  

    int max_size = 0; // для размера самого большого BST

    boolean is_bst = false;

    int min = Integer.MAX_VALUE;  // Для минимального значения в правом поддереве

    int max = Integer.MIN_VALUE;  // Для максимального значения в левом поддереве

  
}

  

class BinaryTree {

  

    static Node root;

    Value val = new Value();

  

    / * Возвращает размер самого большого поддерева BST в двоичном дереве

     (эффективная версия). * /

    int largestBST(Node node) {

  

        largestBSTUtil(node, val, val, val, val);

  

        return val.max_size;

    }

  

    / *gestBSTUtil () обновляет * max_size_ref для размера самого большого BST

     поддерево. Кроме того, если дерево с корнем не является пустым и BST,

     затем возвращает размер дерева. В противном случае возвращает 0. * /

    int largestBSTUtil(Node node, Value min_ref, Value max_ref,

            Value max_size_ref, Value is_bst_ref) {

  

        /* Базовый вариант */

        if (node == null) {

            is_bst_ref.is_bst = true; // Пустое дерево BST

            return 0;    // Размер BST равен 0

        }

  

        int min = Integer.MAX_VALUE;

  

        / * Переменная флага для свойства левого поддерева

         то есть, max (root-> left) <root-> data * /

        boolean left_flag = false;

  

        / * Переменная флага для свойства правого поддерева

         т.е. min (root-> right)> root-> data * /

        boolean right_flag = false;

  

        int ls, rs; // Для хранения размеров левого и правого поддеревьев

  

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

         а) Получить максимальное значение в левом поддереве (хранится в * max_ref)

         б) Проверьте, является ли левое поддерево BST или нет (хранится в * is_bst_ref)

         в) Получить размер максимального размера BST в левом поддереве (обновления * max_size) * /

        max_ref.max = Integer.MIN_VALUE;

        ls = largestBSTUtil(node.left, min_ref, max_ref, max_size_ref, is_bst_ref);

        if (is_bst_ref.is_bst == true && node.data > max_ref.max) {

            left_flag = true;

        }

  

        / * Перед обновлением * min_ref сохраните значение min в левом поддереве. Так что мы

         иметь правильное минимальное значение для этого поддерева * /

        min = min_ref.min;

  

        / * Следующий рекурсивный вызов делает подобное (аналогично левому поддереву)

         задание для правого поддерева * /

        min_ref.min = Integer.MAX_VALUE;

        rs = largestBSTUtil(node.right, min_ref, max_ref, max_size_ref, is_bst_ref);

        if (is_bst_ref.is_bst == true && node.data < min_ref.min) {

            right_flag = true;

        }

  

        // Обновляем минимальное и максимальное значения для родительских рекурсивных вызовов

        if (min < min_ref.min) {

            min_ref.min = min;

        }

        if (node.data < min_ref.min) // Для листовых узлов

        {

            min_ref.min = node.data;

        }

        if (node.data > max_ref.max) {

            max_ref.max = node.data;

        }

  

        / * Если левое и правое поддеревья имеют BST. И левый и правый

         для этого узла сохраняются свойства поддерева, тогда это дерево BST.

         Так что верните размер этого дерева * /

        if (left_flag && right_flag) {

            if (ls + rs + 1 > max_size_ref.max_size) {

                max_size_ref.max_size = ls + rs + 1;

            }

            return ls + rs + 1;

        } else {

            // Поскольку это поддерево не BST, установить флаг is_bst для родительских вызовов

            is_bst_ref.is_bst = false;

            return 0;

        }

    }

  

    public static void main(String[] args) {

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

                50

             / /

            10 60

           / / / /

          5 20 55 70

         ///

        45 65 80

         * /

  

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(50);

        tree.root.left = new Node(10);

        tree.root.right = new Node(60);

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

        tree.root.left.right = new Node(20);

        tree.root.right.left = new Node(55);

        tree.root.right.left.left = new Node(45);

        tree.root.right.right = new Node(70);

        tree.root.right.right.left = new Node(65);

        tree.root.right.right.right = new Node(80);

  

        / * Полное дерево не BST, поскольку 45 находится в правом поддереве 50.

         Следующее поддерево является самым большим BST

             60

            / /

          55 70

          ///

        45 65 80

        * /

        System.out.println("Size of largest BST is " + tree.largestBST(root));

    }

}

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

python3

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

class newNode: 

  

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

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

  
# Возвращает размер наибольшего поддерева BST
# в двоичном дереве (эффективная версия).

def largestBST(node):

      

    # Установите начальные значения для вызова

    #gestBSTUtil ()

    Min = [999999999999] # Для минимального значения в

                         # правильное поддерево

    Max = [-999999999999] # Для максимального значения в

                          # левое поддерево

      

    max_size = [0] # Для размера самого большого BST

    is_bst = [0]

      

    largestBSTUtil(node, Min, Max

                         max_size, is_bst) 

      

    return max_size[0]

  
# majorBSTUtil () обновляет max_size_ref [0]
# для размера самого большого поддерева BST.
# Также, если дерево с корнем в узле
# непустое и BST, затем возвращает размер
# дерево. В противном случае возвращает 0.

def largestBSTUtil(node, min_ref, max_ref, 

                         max_size_ref, is_bst_ref):

      

    # Базовый вариант

    if node == None:

        is_bst_ref[0] = 1 # Пустое дерево BST

        return 0 # Размер BST равен 0

      

    Min = 999999999999

      

    # Флаговая переменная для свойства левого поддерева

    # т.е. max (root.left) <root.data

    left_flag = False

      

    # Флаговая переменная для свойства правого поддерева

    # т.е. min (root.right)> root.data

    right_flag = False

      

    ls, rs = 0, 0    # Для хранения размеров слева и

                     # правильные поддеревья

      

    # Следующие задачи выполняются рекурсивно

    # вызов левого поддерева

    # a) Получить максимальное значение в левом поддереве

    # (Хранится в max_ref [0])

    # b) Проверьте, является ли Левое поддерево BST или

    # not (хранится в is_bst_ref [0])

    # c) Получить размер максимального размера BST в

    # левое поддерево (обновляет max_size [0])

    max_ref[0] = -999999999999

    ls = largestBSTUtil(node.left, min_ref, max_ref, 

                           max_size_ref, is_bst_ref) 

    if is_bst_ref[0] == 1 and node.data > max_ref[0]: 

        left_flag = True

      

    # Перед обновлением min_ref [0] сохраните

    # значение в левом поддереве. Так что у нас есть

    # правильное минимальное значение для этого поддерева

    Min = min_ref[0]

      

    # Следующий рекурсивный вызов делает подобное

    # (аналогично левому поддереву) задание для правого поддерева

    min_ref[0] = 999999999999

    rs = largestBSTUtil(node.right, min_ref, max_ref,

                        max_size_ref, is_bst_ref) 

    if is_bst_ref[0] == 1 and node.data < min_ref[0]: 

        right_flag = True

      

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

    # родительские рекурсивные вызовы

    if Min < min_ref[0]: 

        min_ref[0] = Min

    if node.data < min_ref[0]: # Для листовых узлов

        min_ref[0] = node.data

    if node.data > max_ref[0]: 

        max_ref[0] = node.data

      

    # Если левые и правые поддеревья являются BST.

    # И свойства левого и правого поддерева удерживаются

    # для этого узла, то это дерево BST.

    # Так что верните размер этого дерева

    if left_flag and right_flag:

        if ls + rs + 1 > max_size_ref[0]: 

            max_size_ref[0] = ls + rs + 1

        return ls + rs + 1

    else:

          

        # Так как это поддерево не BST, установите is_bst

        # флаг для родительских вызовов is_bst_ref [0] = 0;

        return 0

  
Код водителя

if __name__ == '__main__':

      

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

    № 50

    # / /

    # 10 60

    # / / / /

    # 5 20 55 70

    # / / /

    # 45 65 80

    root = newNode(50

    root.left     = newNode(10

    root.right     = newNode(60

    root.left.left = newNode(5

    root.left.right = newNode(20

    root.right.left = newNode(55)

    root.right.left.left = newNode(45

    root.right.right = newNode(70)

    root.right.right.left = newNode(65

    root.right.right.right = newNode(80)

  
# Полное дерево не BST, поскольку 45 находится в
# правильное поддерево 50. Следующее поддерево
# самый большой BST
№ 60
# / /
# 55 70
# / / /
# 45 65 80

  

print("Size of the largest BST is"

                  largestBST(root))

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

C #

using System;

  
// C # программа для поиска наибольшего поддерева BST в заданном двоичном дереве

  

public class Node

{

  

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

public class Value

{

  

    public int max_size = 0; // для размера самого большого BST

    public bool is_bst = false;

    public int min = int.MaxValue; // Для минимального значения в правом поддереве

    public int max = int.MinValue; // Для максимального значения в левом поддереве

  
}

  

public class BinaryTree

{

  

    public static Node root;

    public Value val = new Value();

  

    / * Возвращает размер самого большого поддерева BST в двоичном дереве

     (эффективная версия). * /

    public virtual int largestBST(Node node)

    {

  

        largestBSTUtil(node, val, val, val, val);

  

        return val.max_size;

    }

  

    / *gestBSTUtil () обновляет * max_size_ref для размера самого большого BST

     поддерево. Кроме того, если дерево с корнем не является пустым и BST,

     затем возвращает размер дерева. В противном случае возвращает 0. * /

    public virtual int largestBSTUtil(Node node, Value min_ref, Value max_ref, Value max_size_ref, Value is_bst_ref)

    {

  

        /* Базовый вариант */

        if (node == null)

        {

            is_bst_ref.is_bst = true; // Пустое дерево BST

            return 0; // Размер BST равен 0

        }

  

        int min = int.MaxValue;

  

        / * Переменная флага для свойства левого поддерева

         то есть, max (root-> left) <root-> data * /

        bool left_flag = false;

  

        / * Переменная флага для свойства правого поддерева

         т.е. min (root-> right)> root-> data * /

        bool right_flag = false;

  

        int ls, rs; // Для хранения размеров левого и правого поддеревьев

  

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

         а) Получить максимальное значение в левом поддереве (хранится в * max_ref)

         б) Проверьте, является ли левое поддерево BST или нет (хранится в * is_bst_ref)

         в) Получить размер максимального размера BST в левом поддереве (обновления * max_size) * /

        max_ref.max = int.MinValue;

        ls = largestBSTUtil(node.left, min_ref, max_ref, max_size_ref, is_bst_ref);

        if (is_bst_ref.is_bst == true && node.data > max_ref.max)

        {

            left_flag = true;

        }

  

        / * Перед обновлением * min_ref сохраните значение min в левом поддереве. Так что мы

         иметь правильное минимальное значение для этого поддерева * /

        min = min_ref.min;

  

        / * Следующий рекурсивный вызов делает подобное (аналогично левому поддереву)

         задание для правого поддерева * /

        min_ref.min = int.MaxValue;

        rs = largestBSTUtil(node.right, min_ref, max_ref, max_size_ref, is_bst_ref);

        if (is_bst_ref.is_bst == true && node.data < min_ref.min)

        {

            right_flag = true;

        }

  

        // Обновляем минимальное и максимальное значения для родительских рекурсивных вызовов

        if (min < min_ref.min)

        {

            min_ref.min = min;

        }

        if (node.data < min_ref.min) // Для листовых узлов

        {

            min_ref.min = node.data;

        }

        if (node.data > max_ref.max)

        {

            max_ref.max = node.data;

        }

  

        / * Если левое и правое поддеревья имеют BST. И левый и правый

         для этого узла сохраняются свойства поддерева, тогда это дерево BST.

         Так что верните размер этого дерева * /

        if (left_flag && right_flag)

        {

            if (ls + rs + 1 > max_size_ref.max_size)

            {

                max_size_ref.max_size = ls + rs + 1;

            }

            return ls + rs + 1;

        }

        else

        {

            // Поскольку это поддерево не BST, установить флаг is_bst для родительских вызовов

            is_bst_ref.is_bst = false;

            return 0;

        }

    }

  

    public static void Main(string[] args)

    {

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

                50

             / /

            10 60

           / / / /

          5 20 55 70

         ///

        45 65 80

         * /

  

        BinaryTree tree = new BinaryTree();

        BinaryTree.root = new Node(50);

        BinaryTree.root.left = new Node(10);

        BinaryTree.root.right = new Node(60);

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

        BinaryTree.root.left.right = new Node(20);

        BinaryTree.root.right.left = new Node(55);

        BinaryTree.root.right.left.left = new Node(45);

        BinaryTree.root.right.right = new Node(70);

        BinaryTree.root.right.right.left = new Node(65);

        BinaryTree.root.right.right.right = new Node(80);

  

        / * Полное дерево не BST, поскольку 45 находится в правом поддереве 50.

         Следующее поддерево является самым большим BST

             60

            / /

          55 70

          ///

        45 65 80

        * /

        Console.WriteLine("Size of largest BST is " + tree.largestBST(root));

    }

}

  

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


Выход:

Size of largest BST is 6

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

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

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

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

Найти наибольшее поддерево BST в данном двоичном дереве | Комплект 1

0.00 (0%) 0 votes