My accepted Java solution using stack


  • 1
    B

    import java.util.Stack;

    public class Solution {

    Stack<Integer> stack = new Stack<Integer>();
    
    public void inOrder(TreeNode root){
    	if(root != null){
    		inOrder(root.left);
    		stack.push(root.val);
    		inOrder(root.right);
    	}
    }
    
    
    public boolean isValidBST(TreeNode root){
        if(root == null){
            return true;
        }
        
    	inOrder(root);
    	int i = stack.pop();
    	
    	while(!stack.isEmpty()){
    		int j = stack.pop();
    		if(i <= j){
    			return false;
    		}
    		i = j;
    	}
    	
    	return true;
    }
    

    }

    The basic idea is that, first store all values of this tree in-order, from left to parent to right.

    Then if the tree is a binary search tree, values in stack should from maximum to minimum, so we pop each element one by one and compare these elements one by one.

    If a new popped element is greater than the previous one, we can conclude that this isn't a BST.


Log in to reply
 

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