Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
public class Solution { public boolean isValidBST(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function return minMax(root, Integer.MIN_VALUE,Integer.MAX_VALUE); } public boolean minMax(TreeNode root, int min, int max){ if(root == null) return true; if(root.left!=null && (root.left.val >= root.val || root.left.val<=min)){ return false; }//has to add {} if(root.right!=null &&(root.right.val <= root.val || root.right.val>=max)){ return false; } return minMax(root.left,min,root.val)&&minMax(root.right,root.val,max); } }
mistake: when do left and right recursion, check left first then right to avoid some times parent has left only or right only
public class Solution { public boolean isValidBST(TreeNode root) { if(root== null) return true; List<Integer> list = new ArrayList<Integer>(); retrieve(root,list); for(int i =1; i<list.size(); i++){ if(!(list.get(i) > list.get(i-1))) return false; } return true; } // get a list with inorder traversal of the binary search tree public void retrieve(TreeNode node,List<Integer> list){ if(node == null) return ; retrieve(node.left,list); list.add(node.val); retrieve(node.right,list); } }