Question:
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
Analysis:
给出一棵二叉树，判断它是否是二叉搜索树（BST）。
假设BST是这样定义的：它要么是一棵空树，要么是具有以下性质的树：
1）左子树的所有结点的关键码小于根节点的关键码；
2）右子树的所有结点的关键码大于根节点的关键码；
3）左子树和右子树也是二叉搜索树。
思路：对于一棵BST来说，它的中序遍历的值正好是从大到小排列的，因此可以根据中序遍历来判断二叉树是否是BST。
Answer：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isValidBST(TreeNode root) { List<Integer> l = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode p = root; do { while(p != null) { stack.push(p); p = p.left; } if(!stack.isEmpty()) { p = stack.pop(); if(l.size() != 0) { if(p.val <= l.get(l.size()-1)) return false; } l.add(p.val); p = p.right; } } while(p != null || !stack.isEmpty()); return true; } }
LeetCode -- Validate Binary Search Tree
原文：http://www.cnblogs.com/little-YTMM/p/5234736.html