Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
Example
An example:
2 / 1 4 / 3 5
1 /** 2 * Definition of TreeNode: 3 * public class TreeNode { 4 * public int val; 5 * public TreeNode left, right; 6 * public TreeNode(int val) { 7 * this.val = val; 8 * this.left = this.right = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 /** 14 * @param root: The root of binary tree. 15 * @return: True if the binary tree is BST, or false 16 */ 17 public boolean isValidBST(TreeNode root) { 18 // write your code here 19 if (root == null) { 20 return true; 21 } 22 if ((root.left == null) && (root.right == null)) { 23 return true; 24 } 25 26 boolean left = false; 27 boolean right = false; 28 if (root.left == null) { 29 left = true; 30 } 31 else if ((root.left != null) && (root.left.val < root.val)) { 32 left = isValidBST(root.left); 33 }else { 34 return false; 35 } 36 37 if (root.right == null) { 38 right = true; 39 } 40 else if ((root.right != null) && (root.right.val > root.val)) { 41 right = isValidBST(root.right); 42 }else { 43 return false; 44 } 45 46 return left && right; 47 } 48 }
LintCode Validate Binary Search Tree
原文:http://www.cnblogs.com/ly91417/p/5759495.html