二十一：判断二叉树是否是二叉查找树？
二叉查找树：左子树所有结点值均小于它的根结点的值；右子树所有结点值均大于它的根结点值。
别名：二叉搜索树、二叉排序树。
算法一
思路：
根据二叉搜索树特性。
判断当前结点是否是空结点，如果是返回true（空结点属于二叉搜索树）。
判断当前结点值是否在[min,max]（开区间）之间，如果不在返回false。
如果在区间内，则递归检查左右子树是否满足条件。
/*** @description 二叉树是否是二叉搜索树* @param {*} root 二叉树*/function isValidBST(root) {/*** @param {*} root 二叉树* @param {*} min 区间最小值，默认为无穷小* @param {*} max 区间最大值，默认为无穷大*/function dfs(root, min = -Infinity, max = Infinity) {// 如果空结点返回trueif (!root) return true;// 如果不在区间内，返回falseif (root.value <= min || root.value >= max) return false;// 递归左结点，将max值更改为当前结点的值// 同理递归右节点，将min值更改为当前结点的值return dfs(root.left, min, root.value) && dfs(root.right, root.value, max);}return dfs(root);}
算法二
思路：
根据二叉树中序遍历特性，依次输出结点值是有序序列。
根据二叉查找树特性，只需要判断该序列是否是递增序列。
声明一个变量用来记录上一个结点的值，默认值为无穷小。
中序遍历（左/中/右）：判断当前节点值是否小于等于前一个结点值，如果是返回false。
递归中序遍历：
/*** @description 二叉树是否是二叉搜索树 （中序遍历）* @param {*} root 二叉树*/function isValidBST(root) {// 默认值为无穷小let preVal = -Infinity;function dfs(root) {if (!root) return true;const left = dfs(root.left);// 如果上一个结点值大于等于当前结点的值，返回falseif (preVal >= root.val) return false;preVal = root.val;const right = dfs(root.right);// 返回最终结果return left && right;}return dfs(root);}
非递归中序遍历：
/*** @description 二叉树是否是二叉搜索树 （中序遍历）* @param {*} root 二叉树*/function isValidBST(root) {const stack = [];// 上一个结点的值，默认无穷小let preVal = -Infinity;while (stack.length || root) {while (root) {// 入栈stack.push(root);root = root.left;}// 出栈root = stack.pop();// 如果上一个结点值大于等于当前结点的值，返回falseif (preVal >= root.val) return false;preVal = root.val;root = root.right;}// 遍历结束，说明是二叉搜索树return true}