Given a binary tree, determine if it is a valid binary search tree (BST).
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.
解题思路：
本题方法多多，可以采用DFS，当然最简答的方法是采用之前的中序遍历Java for LeetCode 094 Binary Tree Inorder Traversal检查得到的List是否有序即可。
public boolean isValidBST(TreeNode root) {
List<Integer> list=inorderTraversal(root);
if(list.size()==0)
return true;
int temp=list.get(0);
for(int i=1;i<list.size();i++){
if(temp>=list.get(i))
return false;
temp=list.get(i);
}
return true;
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if(root==null)
return list;
if (root.left != null)
list.addAll(inorderTraversal(root.left));
list.add(root.val);
if (root.right != null)
list.addAll(inorderTraversal(root.right));
return list;
}
JAVA实现如下：