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.Example 1:
2 / \ 1 3 Binary tree [2,1,3], return true.Example 2:
1 / \ 2 3Binary tree [1,2,3], return false.
解题思路：中序遍历该树，记录访问过的最大节点的值，所有将要访问的节点的值应该大于该值，通过对每个当前访问的节点与目前最大值进行比较，就可以得出结果。
/** * 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) { //中序遍历，然后将遍历的结果进栈，下一个将要进栈的数一定要大于等于栈顶元素 Stack<Integer> stacknum = new Stack<Integer>(); //本来想用number来记录当前访问的最大值，但是会出现正好用MIN_VAIUE作为节点的特例 //int number=java.lang.Integer.MIN_VALUE; Stack<TreeNode> stacknode=new Stack<TreeNode>(); if(root==null){ return true; }else if(root.left==null && root.right==null){ return true; }else{ //stacknode.push(root); TreeNode p = root; while(!stacknode.empty() || p!=null){ // p = stacknode.pop(); // p=p.left; while(p!=null){ stacknode.push(p); p=p.left; } p=stacknode.pop(); if(stacknum.empty()){ stacknum.push(p.val); }else{ if(stacknum.pop()<p.val){ stacknum.push(p.val); }else{ return false; } } /*if(number<p.val){ number=p.val; }else{ return false; }*/ p=p.right; } return true; } } };