首页 > 代码库 > [LeetCode]98 Validate Binary Search Tree
[LeetCode]98 Validate Binary Search Tree
https://oj.leetcode.com/problems/validate-binary-search-tree/
http://blog.csdn.net/linhuanmars/article/details/23810735
/**
* 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) {
// 一个bst要求
// 左树 也是bst，左边最大值 小于 当前值
// 右树 也是bst，右边最小值 大于 当前值
if (root == null)
return true;
return getValues(root).valid;
}
private Values getValues(TreeNode node)
{
int min = node.val;
int max = node.val;
boolean valid = true;
if (node.left != null)
{
Values left = getValues(node.left);
valid &= left.valid;
valid &= (left.max < node.val);
if (valid)
min = Math.min(left.min, min);
}
if (node.right != null)
{
Values right = getValues(node.right);
valid &= right.valid;
valid &= (right.min > node.val);
if (valid)
max = Math.max(right.max, max);
}
return new Values(min, max, valid);
}
static class Values
{
Values(int min, int max, boolean valid)
{
this.min = min;
this.max = max;
this.valid = valid;
}
int min;
int max;
boolean valid;
}
}[LeetCode]98 Validate Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。