题目链接: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. * */ public class ValidateBinarySearchTree { public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } // 74 / 74 test cases passed. // Status: Accepted // Runtime: 292 ms // Submitted: 0 minutes ago public boolean isValidBST(TreeNode root) { return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } public boolean isValidBST(TreeNode root, int min, int max) { if(root == null) return true; boolean l = true; boolean r = true; if(root.val >= min && root.val <= max) { // min <= root.val <= max if(root.val != Integer.MIN_VALUE) l = isValidBST(root.left, min, root.val - 1); else {// 当root.val = Integer.MIN_VALUE时 if(root.left != null) l = false; //如果还有左节点,则不是二叉排序树 } if(root.val != Integer.MAX_VALUE) r = isValidBST(root.right, root.val + 1, max); else {// 当root.val = Integer.MAX_VALUE时 if(root.right != null) l = false; //如果还有右节点,则不是二叉排序树 } return l && r; } else return false; } public static void main(String[] args) { // TODO Auto-generated method stub } }
[LeetCode 98] Validate Binary Search Tree
原文:http://blog.csdn.net/ever223/article/details/44560345