题目：
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
思路：
1) 递归，两边夹
package bst; public class ValidateBinarySearchTree { public boolean isValidBST(TreeNode root) { return isValidBST(root, false, Integer.MIN_VALUE, false, Integer.MAX_VALUE); } private boolean isValidBST(TreeNode root, boolean reachMin, int min, boolean reachMax, int max) { if (root == null) return true; int value = root.val; if (value < min || value > max) return false; if (!reachMin && value == Integer.MIN_VALUE) { if (root.left != null) return false; return isValidBST(root.right, true, value, reachMax, max); } else if (!reachMax && value == Integer.MAX_VALUE) { if (root.right != null) return false; return isValidBST(root.left, reachMin, min, true, value); } else if (value > min && value < max) { return isValidBST(root.left, reachMin, min, reachMax, value) && isValidBST(root.right, reachMin, value, reachMax, max); } return false; } public static void main(String[] args) { // TODO Auto-generated method stub } }
2) 类似于中序遍历
package bst; public class ValidateBinarySearchTree { private boolean firstNode = true; private int lastValue = 0; public boolean isValidBST(TreeNode root) { if (root == null) return true; if (!isValidBST(root.left)) return false; if (!firstNode && root.val <= lastValue) return false; firstNode = false; lastValue = root.val; if (!isValidBST(root.right)) return false; return true; } public static void main(String[] args) { // TODO Auto-generated method stub } }
LeetCode - Validate Binary Search Tree
原文：http://www.cnblogs.com/shuaiwhu/p/5116903.html