Java solution based on inorder traversal


  • 0
    R

    The basic idea is the traverse the whole binary tree and store the val in each node.
    The returned list should be sorted in increased order, otherwise the tree is not BST.

    public boolean isValidBST(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        val_list(root, list);
        if(list.size()>1)
            for(int i=1;i<list.size();i++){
            	if(list.get(i-1)>=list.get(i)){
            		return false;
            	}
            }
        
        return true;
    }
    public void val_list(TreeNode node,ArrayList<Integer> list){
    	if(node==null){
    		return;
    	}
    	val_list(node.left,list);
    	list.add(node.val);
    	val_list(node.right, list);
    }

  • 1
    L

    I had the same idea with you, but I'm not sure that a tree whose in-order traversal result is a sorted list must be a binary search tree. But I think you can use a class variable to simplify it, below is my code:

    public class Solution
    {
        private TreeNode previous;
        private boolean inorderTravel(final TreeNode root)
        {
            if (root != null)
            {
                if (inorderTravel(root.left))
                {
                    if (previous.val < root.val)
                    {
                        previous = root;
                        
                        return inorderTravel(root.right);
                    }
                }
                
                return false;
            }
            else
            {
                return true;
            }
        }
        
        public boolean isValidBST(TreeNode root)
        {
            previous = new TreeNode(Integer.MIN_VALUE);
            
            return inorderTravel(root);
        }
    }

  • 0
    J

    If you think about how to generate a binary search tree, you will know why it is a good idea.

    Your solution should not use Integer.MIN_VALUE. It will failed when root.val is Integer.MIN_VALUE. null is good for you to eliminate this problem.


Log in to reply
 

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