题目地址：

https://www.lintcode.com/problem/largest-bst-subtree/description

给定一棵二叉树， 求其最大的二叉搜索子树。这里最大指的是含的节点最多。返回该BST的节点个数。

思路是DFS。遍历到某个节点的时候，向上层递归返回一个数组$a$，其中$a[0]$存以当前节点为树根的子树有多少个节点，如果当前子树不是BST则规定$a[0]=-1$，$a[1]$存以当前节点为树根的子树的最小值，$a[2]$存最大值，如果是当前节点是null，则返回null给上层。这样遍历到一个节点的时候，可以先从其左右子树得到这个数组$a$，如果其中一棵子树不是BST，那就直接返回给上层当前节点的子树也不是BST；如果左右子树都是BST，但是当前节点小于等于左子树的最大值，或者大于等于右子树的最小值，此时也不是BST，返回给上层；否则的话说明当前子树是BST，则更新答案，然后把信息返回给上层。DFS完毕后看一下答案里存的节点个数即可。代码如下：

public class Solution { // 存一下当前找到的BST节点最多是多少 private int res; /** * @param root: the root * @return: the largest subtree's size which is a Binary Search Tree */ public int largestBSTSubtree(TreeNode root) { // Write your code here dfs(root); return res; } // 返回一个数组，第0个数是以cur为根的子树节点个数， // 如果不是BST则第0个数赋值为-1，第1个数是该子树的最小值，第2个数是该子树的最大值； // 如果是空树则返回null private int[] dfs(TreeNode cur) { if (cur == null) { return null; } int[] left = dfs(cur.left), right = dfs(cur.right); if (left == null && right == null) { res = Math.max(res, 1); return new int[]{1, cur.val, cur.val}; } if (left == null) { if (right[0] == -1 || cur.val >= right[1]) { return new int[]{-1, 0, 0}; } else { res = Math.max(res, 1 + right[0]); return new int[]{1 + right[0], cur.val, right[2]}; } } if (right == null) { if (left[0] == -1 || cur.val <= left[2]) { return new int[]{-1, 0, 0}; } else { res = Math.max(res, 1 + left[0]); return new int[]{1 + left[0], left[1], cur.val}; } } if (left[0] == -1 || right[0] == -1 || cur.val <= left[2] || cur.val >= right[1]) { return new int[]{-1, 0, 0}; } else { res = Math.max(res, 1 + left[0] + right[0]); return new int[]{1 + left[0] + right[0], left[1], right[2]}; } } } class TreeNode { int val; TreeNode left, right; public TreeNode(int val) { this.val = val; } }

时间复杂度$O(n)$，空间$O(h)$。