首页 > 代码库 > LeetCode OJ - Validate Binary Search Tree

LeetCode OJ - Validate Binary Search Tree

验证二叉树是否是查找树,可以通过查看它的中序遍历是否是升序的。

下面是AC代码:

 1 /**
 2      * Given a binary tree, determine if it is a valid binary search tree (BST).
 3      * solution :
 4      * inorder sequence is an ascending sequence!
 5      * @param root
 6      * @return
 7      */
 8     public boolean isValidBST(TreeNode root){
 9         if(root == null)
10             return true;
11         LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
12         //stack.push(root);
13         
14         TreeNode p = root;
15         TreeNode pre = null;
16         while(p!=null||!stack.isEmpty()){
17             if(p!=null){
18                 stack.push(p);
19                 p = p.left;
20             }else{
21                 p = stack.pop();
22                 if(pre!=null && pre.val>=p.val)
23                     return false;
24                 pre = p;
25                 p = p.right;
26             }
27         }
28         return true;
29     }