版权声明：本文为博主原创文章，未经博主允许不得转载。
难度：入门
要求：
给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵BST定义为：
节点的左子树中的值要严格小于该节点的值。
节点的右子树中的值要严格大于该节点的值。
左右子树也必须是二叉查找树。
一个节点的树也是二叉查找树。
样例:
一个例子：
2
/ \
1 4
/ \
3 5
上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.
思路：
方法一： 根据定义递归验证
方法二： 二叉查找树中序遍历可以得到一个递增的序列
这里我们实现方法二:
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
public boolean isValidBST(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
//遍历
inOrder(root, list);
//校验
boolean flag = true;
int cur = Integer.MIN_VALUE;
if(list.size() > 0){
cur = list.get(0);
list.remove(0);
}
for(int i : list){
if(i <= cur){
flag = false;
break;
}else{
cur = i;
}
}
return flag;
}
/**
* 二叉查找树中序遍历可以得到一个递增的序列
*
**/
private void inOrder(TreeNode node, List<Integer> list){
if(node == null){
return;
}
inOrder(node.left, list);
list.add(node.val);
inOrder(node.right, list);
return;
}
}
