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
Binary tree [2,1,3], return true.
Example 2:
1
/
2 3
Binary tree [1,2,3], return false.
题意：判断一个二叉树是不是二叉查找树，即左子树所有节点的值都小于根节点，右子树所有节点的值都大于根节点，左右子树也都是二叉查找树（BST）。
思路：可以找出左子树中的最大点，右子树中的最小点，如果根节点大于左边最大的，并且小于右边最小的，且左右子树也都是BST，则满足BST的条件。
class Result {
long max = Long.MIN_VALUE;
long min = Long.MAX_VALUE;
boolean valid = true;
}
public boolean isValidBST(TreeNode root) {
return helper(root).valid;
}
public Result helper(TreeNode root) {
Result res = new Result();
if (root == null) {
return res;
}
Result left = helper(root.left);
Result right = helper(root.right);
if (!left.valid || !right.valid) {
res.valid = false;
return res;
}
if (left.max < root.val && right.min > root.val) {
res.min = Math.min(left.min, root.val);
res.max = Math.max(right.max, root.val);
return res;
} else {
res.valid = false;
return res;
}
}
