my java dfs stack traditional solution


  • 0
    C
    public class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null)
            return true;
        
        Stack <TreeNode> s = new Stack<TreeNode>();
        
        s.add(root);
        
        while(s.isEmpty() == false)
        {
        TreeNode x = s.pop();
        
        if(x.left != null && x.val<=getmax(x.left))
            return false;
        if(x.right != null && x.val>=getmin(x.right))
            return false;
        if(x.right != null) 
            s.add(x.right);
        if(x.left != null) 
            s.add(x.left);
        }
        return true;
    }
    
    public int getmax(TreeNode n)
    {
        int tmp = Integer.MIN_VALUE;
        
        Stack <TreeNode> s = new Stack<TreeNode>();
        
        if(n == null)
            return tmp;
        
        s.add(n);
        while(s.isEmpty() == false)
        {
            TreeNode x = s.pop();
            tmp=tmp>x.val?tmp:x.val;
            if(x.right != null)
            s.add(x.right);
            if(x.left != null)
            s.add(x.left);
            
        }
        return tmp;
    }
    
    public int getmin(TreeNode n)
    {
        int tmp = Integer.MAX_VALUE;
        
        Stack <TreeNode> s = new Stack<TreeNode>();
        
        if(n == null)
            return tmp;
        
        s.add(n);
        while(s.isEmpty() == false)
        {
            TreeNode x = s.pop();
            tmp=tmp>x.val?x.val:tmp;
            if(x.right != null)
            s.add(x.right);
            if(x.left != null)
            s.add(x.left);
            
        }
        return tmp;
    }
    

    }


Log in to reply
 

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