Java solution based on BST Inorder Traversal


  • 1

    The Basic idea is inorder traversal of bst

    1 Recursive

    public class Solution {
        TreeNode pre = null;
        public boolean isValidBST(TreeNode root) {
            return inOrder(root);
        }
        
        public boolean inOrder(TreeNode root){
            if(root==null) return true;
            if(!inOrder(root.left)) return false;
            if(pre==null){
                pre= new TreeNode(root.val);
            }else{
                if(root.val<=pre.val)
                    return false;
                pre.val=root.val;
            }
            return inOrder(root.right);
        }
    }
    
    

    2 Iterative

    public class Solution {
        public boolean isValidBST(TreeNode root) {
            if(root==null) return true;
            TreeNode pre = null;
            Stack<TreeNode> s = new Stack<>();
            TreeNode cur = root;
            while(!s.isEmpty() || cur!=null){
                while(cur!=null){
                    s.push(cur);
                    cur=cur.left;
                }
                cur = s.pop();
                if(pre==null){
                    pre=new TreeNode(cur.val);
                }else{
                    if(cur.val<=pre.val)
                        return false;
                    pre.val = cur.val;
                }
                cur=cur.right;
            }
            return true;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.