题目
找出二叉树中最大的子树，该子树为二叉搜索树。所谓最大的子树就是指结点数目最多的子树。
分析
该题目是要找出二叉树中最大的子树，该子树必须是二叉搜索树(BST)。子树的概念需要重点关注一下，以下面一棵二叉树为例
____10____ / \ __5_ 15_ / \ \ 1 8 7
那么该二叉树最大的为BST的子树应该算subtree(1)还是subtree(2)呢？
____ 10____ / \ __5_ 15 -------- subtree (1) / \ 1 8
__5_ / \ -------- subtree (2) 1 8
根据维基百科对子树的定义，一棵二叉树T的子树由T的某个结点和该结点所有的后代构成。也就是说，该题目中，subtree(2)才是正确的答案，因为subtree(1)不包含结点7，不满足子树的定义。
基本解法—自顶向下
最自然的解法是以根结点开始遍历二叉树所有的结点，判定以当前结点为根的子树是否是BST，如果是，则该结点为根的BST就是最大的BST。如果不是，递归调用左右子树，返回其中包含较多结点的子树。
void maxSubTree(pNode root, int &max, pNode &ret)
{
if (!root) {
max = 0;
ret = root;
return;
}
if (isBST(root)) { //以root为根结点的树为BST，则设置结果为root并返回。该函数请参看博文《判定一颗树是否是二叉搜索树》
max = size(root);
ret = root;
return;
}
int lmax, rmax;
pNode lret, rret;
maxSubTree(root->left, lmax, lret); //找出左子树中为BST的最大的子树
maxSubTree(root->right, rmax, rret); //找出右子树中为BST的最大的子树
max = lmax > rmax ? lmax : rmax; //设定结点最大数目
ret = lmax > rmax ? lret : rret; //设定为BST的最大子树的根结点
}
优化方法—自底向上
由于自顶向下的方法每次都要调用isBST来判断当前结点为根结点的子树是否是二叉搜索树，每次调用时间为O(n)，其实这里面有些重复的判断。如果采用自底向上的方法，我们在判断上面结点为根的子树是否是BST之前已经知道底部结点为根的子树是否是BST。因此只要以底部结点为根的子树不是BST，则以它上面结点为根的子树一定不是BST。
判定一颗树是否是BST的方法如下：
1）每个结点的左右子树都是BST
2）每个结点的值大于左子树的最大值
3）每个结点的值小于右子树的最小值
因此采用自底向上的方法时，我们需要向上传递一些信息，包括子树的最大值和最小值以及子树的大小。显然，树的大小=左子树大小+右子树大小+1。
// 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;
findLargestBSTSubtree(root, min, max, maxNodes, largestBST);
return largestBST;
}