LeetCode 98. Validate Binary Search Tree

题目：

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.The right subtree of a node contains only nodes with keys greater than the node's key.Both the left and right subtrees must also be binary search trees.

 

Example 1:

2 / \ 1 3 Input: [2,1,3] Output: true

Example 2:

5 / \ 1 4   / \   3 6 Input: [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.

---

这道题乍一看一道easy啊，然而太多坑了！！！刚开始就想着直接递归的时候比较root和left/right看它们的val符不符合要求，没想到遇到这么一个case：

看了答案发现还得比较当前的root分别和左边最大的数/右边最小的数相比是否满足要求，嗯，然后就写了个helper里面加了min和max，初始化为Integer.MIN和MAX，然后在helper里面比较当前的root和这俩数，然后再递归的时候也同时要更新这个min和max，比如左边的max就要变成当前的val，右边的min也要变成当前的val。嗯，快乐地提交了，还是错了，case：[2147483647]，我……佛了，只能按照答案给的用Integer先设成null了。太多小细节踩坑了。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Validate Binary Search Tree.

Memory Usage: 38.7 MB, less than 7.81% of Java online submissions for Validate Binary Search Tree.

/** * 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) { return helper(root, null, null); } private boolean helper(TreeNode root, Integer min, Integer max) { if (root == null) { return true; } if ((max != null && root.val >= max) || (min != null && root.val <= min)) { return false; } return helper(root.left, min, root.val) && helper(root.right, root.val, max); } }

还有别的迭代的做法以及直接inorder的做法，暂时放弃。