我是前端西瓜哥，今天做一道 medium 难度的算法题：判断一棵二叉树是否为二叉搜索树。
LeetCode 上对应的题目为：
•98 题：https://leetcode-cn.com/problems/validate-binary-search-tree/•《程序员面试金典（第 6 版）》04.05 题：https://leetcode-cn.com/problems/legal-binary-search-tree-lcci/submissions/
什么是二叉搜索树
首先我们要明确二叉搜索树的定义，否则可能带着错误的理解去做题，最终是南辕北辙。
二叉搜索树（Binary Search Tree，简写 BST）是一种比较特别的二叉树。它需要满足：
1.任意节点的值大于其左子树下的所有节点；2.任意节点的值小于其右子树下的所有节点；
下图就是一个二叉搜索树。
之所以叫二叉搜索树，因为它搜索效率很高，时间复杂度为 O(log n)，对标数组的二分查找。
根据二叉搜索树需要满足的条件，我们可以引申出两个特性：
1.二叉搜索树不能有重复的节点值。但实际开发中的搜索树通常还是会有重复值的，但题目如果没有特别指出，就默认不能有重复值。2.中序遍历二叉搜索树，可以拿到单调递增的序列。
初学者易犯的错误
初学者容易犯的错误，就是递归时，认为只要每个节点大于左节点，小于右节点就是合法的了。
其实这并不对。
根据定义，二叉搜索树要求每个节点要大于左子树的所有节点，右子树同理。注意，是 所有，而不是左子树的根节点。
其实我们可以举个反例，下图二叉树满足 “每个节点大于左节点，小于右节点”，但节点 5 右子树中的节点 0 不满足 “任意节点的值小于其右子树下的所有节点” 这个定义。
正确的思路应该是：每个节点需要大于左子树的最大值，小于右子树的最小值。
解法1：中序遍历是否有序
这个解法是最好理解和实现的，只需要改造一下我们熟悉的中序遍历的代码即可。
虽然我知道：二叉搜索树的一个特性是中序遍历有序。
但我没想到可以倒推，即 如果中序遍历有序，可以说明这是一棵二叉搜索树。所以我没有用这个解法。
function isValidBST(root: TreeNode | null): boolean { let prev = -Infinity; let valid = true; function dfs (root: TreeNode | null) { if (!valid) return; // 确定是不合法的，剪枝 if (root === null) return; dfs(root.left); if (prev >= root.val) { valid = false; return; } prev = root.val; dfs(root.right); } dfs(root); return valid; };
声明一个名为 prev 的变量，用来记录递归到的当前节点时，它的前一个节点的值。
一开始要初始化为负无穷大，来处理第一个递归的节点没有前一个节点的边界情况。
也可以多用一个数组来存储中序遍历得到的序列，实现上会更不容易出错，代价是增加了一些空间复杂度。
另外，LeetCode 的官方题解给出的是 非递归形式 的解法，实在是有点离谱。建议你还是用递归的写法，不容易写错。
解法2：指定树的取值范围
这个解法就比较巧妙。
递归函数除了传入节点，还要传入以这个节点为根节点的整棵树的需要位于的区间 (min, max)。
在递归函数执行中，我们需要做的事情有：
1.判断当前节点是否在 (min, max) 内；2.根据左子树还是右子树调整区间，进行下一轮的递归。具体为：对左节点，它的区间为 (min, root.val)；对右节点，区间为 (root.val, max)。
function isValidBST(root: TreeNode | null): boolean { return isInRange(root, -Infinity, Infinity); }; function isInRange(root: TreeNode | null, min: number, max: number): boolean { if (root === null) return true; if (root.val <= min || root.val >= max) return false; return isInRange(root.left, min, root.val) && // 左 isInRange(root.right, root.val, max); // 右 }
解法3：自底向上
下面介绍的是我自己做这题的解法，不是主流的解法。
解法上的判断逻辑其实和解法 2 相同，但我这个是自底向上的。
思路与 求二叉树深度 一脉相承，先拿到左右子树的返回值，然后再做进一步判断。
简单来说就是，我们先得到左右子树是否为合法二叉搜索树，如果一个不合法，就直接返回 false。
如果合法，接着判断 root.val 是否大于左子树的最大值，是否小于右子树的最小值。
function isValidBST(root: TreeNode | null): boolean { return getMinAndMax(root)[0]; }; // 返回一棵树的 (1)是否为合法二叉搜索树 (2)最小值 (3)最大值。 function getMinAndMax(root: TreeNode): [boolean, number, number] { if (root === null) return [true, Number.MAX_SAFE_INTEGER, Number.MIN_SAFE_INTEGER]; const [lValid, lMin, lMax] = getMinAndMax(root.left); if (!lValid) return [false, -1, -1]; // -1 还是其他值都无所谓，因为已经不合法了。 const [rValid, rMin, rMax] = getMinAndMax(root.right); if (!rValid) return [false, -1, -1]; if (root.val > lMax && root.val < rMin) { return [ true, root.left ? lMin : root.val, root.right ? rMax : root.val ]; } return [false, -1, -1]; }
这种解法实现起来还挺繁琐的，因为要返回 3 个值。
总结
三种解法的时间复杂度都是 O(n)。
最好理解和实现的是中序遍历解法，实现最优雅的是解法 2，我的解法 3 则相当繁琐，勉强能用。
