币圈小鱼儿
【鲸交所】验证二叉搜索树
来源： 数据结构和算法-山大王 wld
问题描述
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
-
节点的左子树只包含小于当前节点的数。
-
节点的右子树只包含大于当前节点的数。
-
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入 :
2/
1 3
输出 : true
示例 2:
输入 :
5/
1 4
/ 3 6输出 : false
解释 : 输入为 : [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
递归写法
做这题之前我们首先要明白什么是二叉搜索树，就是每个节点左子树的值都比当前节点小，右子树的值都比当前节点大。所以看到这里我们最先想到的就是递归，我最先想到的是下面这种写法（注意是错误的）
1public boolean isValidBST(TreeNode root) { 2 if (root == null) 3 return true; 4 if (root.left != null && root.val <= root.left.val || root.right != null && root.val >= root.right.val) 5 return false; 6 return isValidBST(root.left) && isValidBST(root.right); 7}
如果一个结点是空的，我们默认他是有效的二叉搜索树，否则如果左节点不为空，我们要判断是否大于左节点的值，如果右节点不为空，我们还要判断小于右节点的值，然后我们再以左右两个子节点用相同的方式判断。看起来好像没什么问题，但我们好像忽略了一个每个节点的上限和下限，比如下面这棵树
注意 6 这个节点不光要小于 15 而且还要大于 10，所以这里的每一个节点都是有一个范围的，上面的代码我只判断了 6 比 15 小，但没有和 10 进行比较，所以代码是错误的。这里我们来给每个节点添加一个范围，如果不在这个范围之内直接返回 false，比如 6 的范围是 (10,15)，很明显他不在这个范围内，所以他不是二叉搜索树。根节点的范围我们从 Long.MIN_VALUE 到 Long.MAX_VALUE，来看下代码
1public boolean isValidBST(TreeNode root) { 2 return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); 3} 4 5public boolean isValidBST(TreeNode root, long minVal, long maxVal) { 6 if (root == null) 7 return true; 8 // 每个节点如果超过这个范围，直接返回 false 9 if (root.val >= maxVal || root.val <= minVal) 10 return false; 11 // 这里再分别以左右两个子节点分别判断， 12 // 左子树范围的最小值是 minVal，最大值是当前节点的值，也就是 root 的值，因为左子树的值要比当前节点小 13 // 右子数范围的最大值是 maxVal，最小值是当前节点的值，也就是 root 的值，因为右子树的值要比当前节点大 14 return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal); 15}
中序遍历递归
根据二叉搜索树的性质我们知道，中序遍历二叉搜索树，遍历的结果一定是有序的。中序遍历时，判断当前节点是否大于中序遍历的前一个节点，也就是判断是否有序，如果不大于直接返回 false。
1 // 前一个结点，全局的 2TreeNode prev; 3 4public boolean isValidBST(TreeNode root) { 5 if (root == null) 6 return true; 7 // 访问左子树 8 if (!isValidBST(root.left)) 9 return false; 10 // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点直接返回 false。 11 if (prev != null && prev.val >= root.val) 12 return false; 13 prev = root; 14 // 访问右子树 15 if (!isValidBST(root.right)) 16 return false; 17 return true; 18}
中序遍历非递归
如果对树的中序遍历比较熟悉的话 ，这里面也有树的中序遍历的递归和非递归两种写法。我们完全可以把上面中序遍历的递归改为非递归。
1public boolean isValidBST(TreeNode root) { 2 if (root == null) 3 return true; 4 Stack stack = new Stack<>(); 5 TreeNode pre = null; 6 while (root != null || !stack.isEmpty()) { 7 while (root != null) { 8 stack.push(root); 9 root = root.left; 10 } 11 root = stack.pop(); 12 if (pre != null && root.val <= pre.val) 13 return false; 14 // 保存前一个访问的结点 15 pre = root; 16 root = root.right; 17 } 18 return true; 19}
总结
这题可能最容易理解的是第一种解法，我们只需要给每个节点添加一个范围，然后再分别遍历每个节点，查看是否都在指定的范围内，只要有一个不在范围内，说明不是二叉搜索树，直接返回 false。
后面两种写法是根据二叉搜索树中序遍历的特点来判断，因为二叉搜索树中序遍历的结果是升序的，我们就按照二叉树中序遍历的方式来遍历这棵二叉树，然后在遍历的时候顺便保存一下前一个访问的结点，判断当前节点是否大于前一个结点的值，如果不大于直接返回 false。
- 免责声明
- 世链财经作为开放的信息发布平台，所有资讯仅代表作者个人观点，与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论，请提供相关材料，发送到：2785592653@qq.com。
- 风险提示：本站所提供的资讯不代表任何投资暗示。投资有风险，入市须谨慎。
- 世链粉丝群：提供最新热点新闻，空投糖果、红包等福利，微信：juu3644。
