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

Given a binary tree, I want to find out the largest subtree which is a BST in it.

幼稚的做法：

我心里有一个天真的做法，我参观了树的每一个节点，这个节点传递给isBST功能。我还将跟踪节点的数目中的子树，如果它是一个BST

I have a naive approach in mind where I visit every node of the tree and pass this node to a isBST function. I will also keep track of the number of nodes in a sub-tree if it is a BST.

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

Is there a better approach than this ?

推荐答案

我已经发布了完整的解决方案，并解释在我的博客：

I have posted the full solution and explanation in my blog:

的http：// www.leet code.com / 2010/11 /最大的二进制搜索树BST-in.html

我们的想法是做一个深度优先遍历并通过最小值和最大值的自下而上，而不是自上而下的。换句话说，我们验证了更深的节点之前，我们验证，如果上述的节点满足BST要求。

The idea is to do a depth-first traversal and pass min and max values bottom-up instead of top-down. In other words, we verify the deeper nodes before we verify if the above nodes satisfy the BST requirements.

这样做的主要原因是，当一个节点不符合BST性能，最重要的是子树（包括此节点以及）也必须不可以满足BST的要求。

The main reason of doing this is when one of the nodes does not satisfy the BST properties, all subtrees above (which includes this node as well) must also not satisfy the BST requirements.

相比于自上而下的方法，自底向上的方法是这样一个真棒的选择，因为该结果中节点的总数，可以向上传递树。这让我们可以重新计算了一遍又一遍。对于一个子树的节点的总数仅仅是其左，右子树的节点加一的总数

As compared to the top-down approach, the bottom-up approach is such an awesome choice because the results for total number of nodes could be passed up the tree. This saves us from recalculating over and over again. The total number of nodes for a subtree is simply the total number of nodes of its left and right subtrees plus one.

这个算法运行在O（n）的时间复杂度和O（1）空间，这是因为有效的，因为它可以。 （其中N是节点的二进制树中的总数）。

This algorithm runs in O(N) time complexity and O(1) space, which is as efficient as it can be. (where N is the total number of nodes in the binary tree).

下面是C ++ code，它的工作原理。实施棘手的部分是照顾如何最小值和最大值是通过自下而上的。请注意，我，因为它们是在树的底部初始化未初始化最小和最大值。

Below is the C++ code that works. The tricky part of the implementation is taking care of how min and max values are passed bottom-up. Please note that I did not initialize min and max values as they are initialized in the bottom of the tree.

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