Hot100-验证二叉搜索树

错误代码：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isValidBST(TreeNode root) { //开始就保障他的左右集合以及 if(root==null) return true; TreeNode r=null;TreeNode l=null; if(root.right!=null) r=root.right; if(root.left!=null) l=root.left; if(l!=null&&l.val>=root.val||r!=null&&r.val<=root.val) return false; else{ isValidBST(l); isValidBST(r); } return true; } }

误区：

1.你只考虑了在单一树中存在数父子兄弟错误

2.代码if shit 比较过于复杂，都什么跟什么

3.完全忽视数据范围

树中节点数目范围在[1, 104] 内

-231 <= Node.val <= 231 - 1(31是指数)

正确解法：

class Solution { public boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } //根据条件，设置区间Long.MIN_VALUE, Long.MAX_VALUE public boolean isValidBST(TreeNode node, long lower, long upper) { if (node == null) { return true;//为null，如果是头节点：也是符合的，不是头节点：不符合 } if (node.val <= lower || node.val >= upper) { return false; } return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper); //我们要检查值是否满足，左儿子，上限为父值；右儿子，下限为父值； 那么，如何检查孙子中存在的过小/过大问题 } }

最妙的的点：

如何检查孙子中存在的过小/过大问题

传递子孙上下限，左孙不能大于爷爷，右孙不能小于爷爷，相邻三代为一个传递系统，将规矩延续下去，爸爸当爷爷，孙子当爸爸，代代相传

暂时无法在飞书文档外展示此内容