Нахождение самого большого поддерева в BST

Дерево является BST, если его обход по порядку дает вам элементы в отсортированном порядке. Вы можете использовать этот код здесь, если хотите пример реализации: http://placementsindia.blogspot.com/2007/12/c-program-to-check-whether-binary-tree.html

Запуск время O (N), где N = количество узлов.

Считать дерево BST, если два корневых поддерева являются BST, неверно (и для человека, который удалил свой ответ, предлагающий это решение: вам не следовало удалять свой ответ, лично я не собирался отрицать вас и из плохого, но, казалось бы, хорошего решения можно многому научиться, как и из хорошего). Контрпример:

    3
   / \
  2   4
 / \
1  5

Теперь, чтобы получить самое большое поддерево, которое является BST, рассмотрим это дерево:

    3
   / \
  2   4
 / \
1  5

Обход в порядке: 1 2 5 3 4. Я думаю, вы можете решить свою исходную проблему, найдя отсортированное по максимальной длине непрерывная подпоследовательность в обходе по порядку. Вы просто должны быть осторожны, чтобы не выбирать последовательности, которые не описывают BST. Например, для:

    10
   / \
  2   14
 / \  |
1  5  20

Inorder-traversal - 1 2 5 10 20 14. Не выбирайте 20. Я думаю, что этого можно добиться, убрав элементы до тех пор, пока их выбор не имеет смысла. Например, когда вы достигнете 14, отбросьте 20. Я не уверен, что это можно сделать эффективно. Отредактирую свой пост, если найду точный способ.

Думаю, проблема, которую вы пытаетесь решить, заключается в поиске самого большого (с большим количеством узлов) BST в BT. В этом случае вам нужно будет пройти все узлы дерева, проверяя, является ли он BST, и как только вы найдете один, вам нужно будет проверить, больше ли в нем узлов, чем самый большой из найденных на данный момент.

class TreeNode
{
    public int value;
    public TreeNode left;
    public TreeNode right;
}

void LargestBST(TreeNode bt, IDictionary<TreeNode, bool> isBST, IDictionary<TreeNode, int> nodeCount, ref TreeNode largestBST)
{
    if (bt == null)
        return;
    if (IsBST(bt, isBST) && (largestBST == null || NodeCount(bt, nodeCount) > NodeCount(largestBST, nodeCount)) 
        largestBST = bt;
    else
    {
        LargestBST(bt.left, isBST, nodeCount, ref largestBST);
        LargestBST(bt.Right, isBST, nodeCount, ref largestBST);
    }
}

bool IsBST(TreeNode node, IDictionary<TreeNode, bool> isBST)
{
    if (node == null)
        return true;

    bool result;
    if (!isBST.TryGetValue(node, out result))
    {
        TreeNode maxLeft = Max(node.Left);
        TreeNode minRight = Min(node.Right);
        result = (maxLeft == null || maxLeft.value <= node.value) &&
                 (minRight == null || minRight.value >= node.value) &&
                 IsBST(node.left, isBST) && IsBST(node.Right, isBST);
        isBST.Add(node, result);
    }
    return result;
}

TreeNode Max(TreeNode node)
{
    if (node == null)
        return null;
    while (node.right != null)
        node = node.right;
    return node;
}

TreeNode Min(TreeNode node)
{
    if (node == null)
        return null;
    while (node.left != null)
        node = node.left;
    return node;
}

int NodeCount(TreeNode node, IDictionary<TreeNode, int> nodeCount)
{
    if (node == null)
        return 0;
    int result;
    if (!nodeCount.TryGetValue(node, out result))
    {
        result = 1 + NodeCount(node.left, nodeCount) + NodeCount(node.right, nodeCount);
        nodeCount.Add(node, result);
    }
    return result;
}

Я думаю, вы могли бы избежать проверки, является ли каждый узел корнем BST, работая сверху вниз, а не снизу вверх. Если поддерево является BST, оно будет больше, чем любое поддерево само по себе, поэтому вам не нужно проверять внутри поддерева, прошло ли оно проверку isBST. Тогда вам просто нужно, чтобы isBST вернул размер действительного дерева и сохранил его вместе с указателем на корень поддерева, если вам нужно иметь возможность найти его снова, вместо того, чтобы просто знать, насколько велико самое большое дерево.

ОБНОВЛЕНИЕ:

Часть кода, размещенного здесь, чтобы проверить, является ли что-то BST, в некоторых случаях не сработает, поскольку они проверяют только родительский узел узла.

Возьмем, например:

  10 
 / \ 
4 99 
 / 
2 
 

Это недопустимый BST (2 не соответствует позиции 10), но если вы не отправите минимальное и максимальное значение вниз по дереву, вы неправильно проверите его как действительное. Этот псевдокод учитывает это.

main
{
    Verify(root, MIN_VALUE, MAX_VALUE)
}

boolean Verify(node , min, max)
{

 if(node == null)
   return true;

  if(node.value > min &&
     node.value < max &&
     Verify(node.leftchild, min, node.value) &&
     Verify(node.rightchild,node.value,max)
  {
      return true;
  }
  else
  {
      return false;
  }
}

int getMinMaxValue(Node* root, bool isMin)
{
   if (!root)
   {
      // Not real limits...
      return (isMin ? INT_MAX : INT_MIN);
   }
   int leftVal = getMinMaxValue(root->left, isMin);
   int rightVal = getMinMaxValue(root->right, isMin);
   if (isMin)
   {
      return min(root->value, min(leftVal, rightVal));
   }
   else
   {
      return max(root->value, max(leftVal, rightVal));
   }
}

bool isBST(Node* root)
{
   if (!root)
   {
      return true;
   }

   Node* left = root->left;
   Node* right = root->right;

   if (left)
   {
      if (getMinMaxValue(left, false) > root->value)
      {
         return false;
      }
   }

   if (right)
   {
      if (getMinMaxValue(right, true) < root->value)
      {
         return false;
      }
   }

   return isBST(left) && isBST(right);
}

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

Чтобы проверить, является ли узел корнем BST, мы должны рекурсивно проверить каждого левого и правого потомков. Если вы начнете с корня, вам придется повторить все дочерние элементы, прежде чем вы сможете решить, является ли корень двоичного дерева BST или нет. Поэтому нет смысла вызывать isBST для каждого узла. Вот мой подход

1. Начать с корня
2. Найти максимальное значение слева и справа
3. Если не максимальное значение слева и справа, вернуть "NOT BST"
4. , если слева BST, проверьте, не { {1}} больше максимального. Если да, сохраните его и верните "NOT BST"
5. , если BST справа, проверьте, не превышает ли он максимальное значение на данный момент. Если да, сохраните его и верните "NOT BST"
6. Если left и right являются BST, есть новый BST с текущим корнем как ROOT и с количеством оставшихся узлов + right + 1

Пара проблем при выполнении этой работы - это сохранение максимального значения, для которого я использовал переменную ref MaxNumNodes. maxbst withh имеют корень самого большого BST, найденного при возврате функции.

public int MaxBST(Node root, int min, int max, ref Node maxbst, 
        ref int MaxNumNodes)
    {
        if (root == null) return 0;

        //Not a BST
        if (root.data < min || root.data > max) return -1;

        //Find Max BST on left
        int left = MaxBST(root.left, min, root.data, ref maxbst, 
                                    ref MaxNumNodes);
        //Find Max BST on right
        int right = MaxBST(root.right, root.data + 1, max, ref maxbst,
                                            ref MaxNumNodes);

        //Case1: -1 from both branches . No BST in both branches
        if (left == -1 && right == -1) return -1;

        //Case2:No BST in left branch , so choose right 
        //See if the BST on right is bigger than seen so far
        if (left == -1)
        {
            if (right> MaxNumNodes)
            {
                MaxNumNodes = right;
                maxbst = root.right;
            }
            return -1;
        }

        //Case3:No BST in right branch , so choose left 
        //See if the BST on left is bigger than seen so far
        if (right == -1)
        {
            if (left > MaxNumNodes)
            {
                MaxNumNodes = left;
                maxbst = root.left;
            }
            return -1;
        }

        //Case4:Both are BST , new max is left BST + right BST
        maxbst = root;
        return left + right + 1;

    }