leetcode 98. Validate Binary Search Tree 递归验证二叉搜索树

题意

验证一个二叉树是不是二叉搜索树

test cases

[1,1,3] [] [5,1,4,null,null,3,6] [10,5,15,null,null,6,20] [2147483647]

递归一个二叉树，是否是在min，max间的二叉搜索树。

解1

// Runtime: 0 ms, faster than 100.00% of Java online submissions for Validate Binary Search Tree. // Memory Usage: 38.5 MB, less than 8.71% of Java online submissions for Validate Binary Search Tree. public boolean isValidBST(TreeNode root) { return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } public boolean isValidBST(TreeNode node, int min, int max) { if (node == null) return true; if (node.left != null && node.right != null) return node.val >= min && node.val <= max && isValidBST(node.left, min, node.val - 1) && isValidBST(node.right, node.val + 1, max) && node.val > node.left.val && node.val < node.right.val; if (node.left != null) return node.val >= min && node.val <= max && isValidBST(node.left, min, node.val - 1) && node.val > node.left.val; if (node.right != null) return node.val >= min && node.val <= max && isValidBST(node.right, node.val + 1, max) && node.val < node.right.val; return node.val >= min && node.val <= max; }

解2

思路一样，优化代码

public boolean isValidBST(TreeNode root) { return helper(root, null, null); } private boolean helper(TreeNode root, Integer l, Integer r){ if(root == null){ return true; } if(l != null && root.val <= l){ return false; } if(r != null && root.val >= r){ return false; } return helper(root.left, l, root.val) && helper(root.right, root.val, r); }