[LeetCode]Validate Binary Search Tree

注意光判断左子结点小于当前节点右子结点大于当前节点是不够的。比如                  5
                                                                                                                                    /  \
                                                                                                                                  3    8
                                                                                                                                    \
                                                                                                                                     6
就满足条件但不是valid BST。要判断也应该是左子树最大值小于当前节点，右子树最小值大于当前节点。不过这样太麻烦，用top-bottom的方法，开始的范围是(－∞，＋∞)。每次经过一个结点从(low, high)分割成(low, curr.val)和(curr.val, high)像两个子节点递归。不满足就返回false，碰到null返回true。




代码如下：

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public boolean isValidBST(TreeNode root) {
	if (root == null)
	return true;
	return isValid(root, null, null);
	}
	private boolean isValid(TreeNode node, Integer min, Integer max) {
	if (node == null)
	return true;
	if ((max != null && node.val >= max) || (min != null && node.val <= min))
	return false;
	return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
	}
	}

view raw validate binary search tree.java hosted with ❤ by GitHub