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.
題意：判斷一個二叉樹是不是二叉查找樹，即左子樹所有節(jié)點的值都小于根節(jié)點哟绊，右子樹所有節(jié)點的值都大于根節(jié)點睡陪，左右子樹也都是二叉查找樹（BST）。
思路：可以找出左子樹中的最大點匿情，右子樹中的最小點兰迫，如果根節(jié)點大于左邊最大的，并且小于右邊最小的炬称，且左右子樹也都是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;
}
}
