algorithm - 在BST中找到最大的子树

给定一个二叉树，我想找出其中最大的子树是BST。

天真的方法:

我想到一个幼稚的方法，在该方法中，我访问树的每个节点并将该节点传递给isBST函数。如果它是BST，我还将跟踪子树中的节点数。

有没有比这更好的方法了？

最佳答案

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

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;
}

关于algorithm - 在BST中找到最大的子树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2336148/