logo标签列表

在二叉搜索树中查找最大子树

algorithmtreebinary-tree
6

给定一棵二叉树，我想找出其中最大的二叉搜索子树。

朴素的方法：

我心中有一个朴素的方法，遍历树的每个节点并将此节点传递给isBST函数。如果它是一个BST，我还将跟踪子树中的节点数。

是否有比这更好的方法？

1
“最大”的定义是什么？ “最深”的呢？ "节点最多"又是指什么？ - Matt Ball
2
我认为你需要澄清问题。显而易见的答案是整个树都是最大的二叉搜索树。也许你是指最大平衡二叉搜索树吗？ - Joel
3
所有的二叉搜索树都是二叉树，但反过来则不一定成立。 - Larry
我把这个标记为作业。 - Aryabhatta
所谓最大，是指该子树中节点数最多。更明确地说，假设我有一个名为count(node)的函数，它返回子树中节点的数量。 - rakeshr
9个回答
12

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

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

这个算法的思路是进行深度优先遍历，并从底部向上传递最小值和最大值，而不是自顶向下。换句话说，在验证上面的节点是否满足BST要求之前，我们会先验证更深的节点。

这样做的主要原因是当其中一个节点不满足BST属性时，所有上面的子树（包括该节点）也必须不满足BST要求。

与自顶向下的方法相比，自底向上的方法是一个非常好的选择，因为可以将子树的节点总数的结果传递给树上层。这样可以避免反复计算。子树的总节点数就是其左右子树的总节点数加一。

这个算法的时间复杂度为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;
}
空间复杂度是树的高度O(height of tree)，而不是O(1)。 - Prashant Bhanarkar
8

我猜你想要解决的问题是在二叉树中找到最大的（具有更多节点的）二叉搜索树。在这种情况下，您需要遍历所有树节点，检查它是否是一个二叉搜索树，一旦找到一个，您就需要检查它是否比此前找到的最大值更大。

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;
}
2
好的解决方案。请注意，您还可以将节点上的最小/最大值存储为 O(n) 空间，以便更轻松地分析和运行时。（一种对最小/最大值进行路径压缩的排序方法。） - Larry
你的程序是O(n^2)的。从叶子节点向根节点开始，使用自底向上的方法也可以得到O(n)的解决方案。 - Sumit Kumar Saha
2

如果一棵树的中序遍历按顺序给出其元素，则该树是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

现在，为了获得最大的二叉搜索子树，请考虑以下树：

    3
   / \
  2   4
 / \
1  5

中序遍历是1 2 5 3 4。我认为你可以通过在中序遍历中找到最长的排序连续子序列来解决你的原始问题。你只需要小心不要选择那些不能描述BST的序列。例如，对于：
    10
   / \
  2   14
 / \  |
1  5  20

中序遍历是1 2 5 10 20 14。不要选择20。我认为可以通过确保在选择停止有意义的元素时将其解除来实现这一点。例如，当您到达14时，解除20。但我不确定是否可以高效地完成这个任务。如果我找到确切的方法，我会编辑我的帖子。
实际上由于某些原因，我把它和别人建议的“平衡树”混淆了，所以我想到的是平衡树而不是BST。当然，你是正确的。 - Larry
这里我们不能选择10和14。最大的子树是1、2、5，即大小为3。请参见维基百科中子树的定义：“树T的子树是由T中的一个节点及其在T中的所有后代组成的树。[c][1]因此，节点对应于子树（每个节点对应于它自己和所有后代的子树）——对应于根节点的子树是整个树，每个节点都是确定它的子树的根节点；对于任何其他节点对应的子树称为适当子树（类比于术语适当子集）。” - Trying
1

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

1
这不正确。我会在评论中给出一个例子，希望格式不会破坏它。好吧，这是我最初评论的编辑，因为树结构不清晰，所以我会描述它。 根值为10，它的左子节点为5，右子节点为12。12是叶子节点，而5只有一个右子节点，其值为30。 根据您的算法，这是一棵BST，但实际上并不是。 - Fede
嗯，我留下了解决方案，但现在我想想，有一个循环不变量，我可以找到最小/最大值而无需实际查看值，因为如果树不是二叉搜索树，那么最终我会找到破坏它的节点。尽管如此，这仍然有效，但不够好。 - DevDevDev
0
要验证一个节点是否是二叉搜索树的根节点，我们必须递归地检查每个左右子节点。如果从根节点开始，您将不得不递归所有子节点，然后才能确定二叉树的根节点是否为二叉搜索树。因此，对于每个节点调用"isBST"没有任何意义。以下是我的方法：
  1. 从根节点开始
  2. 从左右两侧找到最大值
  3. 如果左右两侧没有最大值，则返回“NOT BST”
  4. 如果左侧是BST，请检查它是否比迄今为止的最大值大。如果是，请存储它并返回“NOT BST”
  5. 如果右侧是BST，请检查它是否比迄今为止的最大值大。如果是，请存储它并返回“NOT BST”
  6. 如果左右两侧都是BST，则有一个新的BST，其当前根为ROOT，节点数为左侧+右侧+1
使其正常工作的几个挑战是存储到目前为止的最大值，我使用了一个引用变量MaxNumNodes。当函数返回时，maxbst将具有找到的最大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;

    }
0
一个可能的解决方案如下 -
int maxNodes = INT.MIN;
Node* lb = NULL; 
int largesBST(Node* root) { 
    largesBST(root, INT.MIN, INT.MAX);
}

int largesBST(Node* p, int MIN, int MAX) { 
     if(!p) { return 0; } 
     if(p->data > MIN || p->data < MAX) { return -1; }
     int lc = largestBST(p->left, p->data, MAX);
     if(lc == -1) { return -1; } 
     int rc = largestBST(p->right, MIN, p->data);
     if(rc == -1) { return -1; } 
     // At this point, cur node is BST
     int curNodes = lc + rc + 1;
     if(curNodes > maxNodes) { 
        maxNodes = curNodes;
        lb = p;
     }
}
0

这不是最优的方法，但您可以对二叉树进行中序遍历并将其存储在数组中，然后找到最长的连续递增序列，这将给出具有最大节点数的BST。复杂度为O(n)用于遍历和O(n)用于搜索，因此仍将是O(n)。

0
为了解决上述问题：
1. 可以对树进行中序遍历。 2. 将其存储在数组中，并找到“最大排序子集”。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接