找到BST中最大的子树

Question

给定一个二叉树,我想找出其中最大的子树BST.

天真的方法:

我有一个天真的方法,我访问树的每个节点,并将此节点传递给isBST函数.如果它是BST,我还将跟踪子树中的节点数.

有比这更好的方法吗？

Answer 1

我在博客中发布了完整的解决方案和解释:

http://www.leetcode.com/2010/11/largest-binary-search-tree-bst-in.html

我们的想法是进行深度优先遍历,并从下到上而不是自上而下传递最小值和最大值.换句话说,我们在验证上述节点是否满足BST要求之前验证更深的节点.

这样做的主要原因是当节点中的一个不满足BST性质,所有的子树上述(包括该节点以及)也必须不能满足BST要求.

与自上而下的方法相比,自下而上的方法是一个非常棒的选择,因为节点总数的结果可以在树上传递.这样可以避免我们一遍又一遍地重新计算.子树的节点总数只是其左右子树的节点总数加1.

该算法在O(N)时间复杂度和O(1)空间中运行,其效率尽可能高.(其中N是二叉树中的节点总数).

下面是可行的C++代码.实现中棘手的部分是如何通过自下而上的方式传递最小值和最大值.请注意,我没有初始化最小值和最大值,因为它们在树的底部初始化.

// Find the largest BST subtree in a binary tree.
// If the subtree is a BST, return total number of nodes.
// If the subtree is not a BST, -1 is returned.
int findLargestBSTSubtree(BinaryTree *p, int &min, int &max,
                   int &maxNodes, BinaryTree *& largestBST) {
  if (!p) return 0;
  bool isBST = true;
  int leftNodes = findLargestBSTSubtree(p->left, min, max, maxNodes, largestBST);
  int currMin = (leftNodes == 0) ? p->data : min;
  if (leftNodes == -1 ||
     (leftNodes != 0 && p->data <= max))
    isBST = false;
  int rightNodes = findLargestBSTSubtree(p->right, min, max, maxNodes, largestBST);
  int currMax = (rightNodes == 0) ? p->data : max;
  if (rightNodes == -1 ||
     (rightNodes != 0 && p->data >= min))
    isBST = false;
  if (isBST) {
    min = currMin;
    max = currMax;
    int totalNodes = leftNodes + rightNodes + 1;
    if (totalNodes > maxNodes) {
      maxNodes = totalNodes;
      largestBST = p;
    }
    return totalNodes;
  } else {
    return -1;   // This subtree is not a BST
  }
}

BinaryTree* findLargestBSTSubtree(BinaryTree *root) {
  BinaryTree *largestBST = NULL;
  int min, max;
  int maxNodes = INT_MIN;   // INT_MIN is defined in <climits>
  findLargestBSTSubtree(root, min, max, maxNodes, largestBST);
  return largestBST;
}

Answer 2

我想你要解决的问题是找到BT中最大的(有更多节点)BST.在这种情况下,您需要遍历所有树节点,检查它是否是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;
}

Answer 3

我认为你可以通过自上而下而不是自下而上的方式来避免检查每个节点是否是 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;
  }
}