C# solution (69 ms) without using long trick


  • 1
    D
    public class Solution 
    {
        public bool IsValidBST(TreeNode root) 
        {
            return IsValidBST(root, new Queue<TreeNode>());
        }
        
        private bool IsValidBST(TreeNode node, Queue<TreeNode> queue)
        {
            if (node == null) return true;
            if (!IsValidBST(node.left, queue)) return false;
            if (queue.Count > 0 && queue.Dequeue().val >= node.val) return false;
            queue.Enqueue(node);
            if (!IsValidBST(node.right, queue)) return false;
            return true;
        }
    }
    

    This uses an in-order depth first search.

    1. If the current node is null we've reached the end of a path. Return true.

    2. Recursively traverse the left subtree. Return false if any nodes are invalid.

    3. The value of the node at the front of the queue should be the largest value in the left subtree as well as being less than the value of the current node. First check the queue for any nodes. If a node exists, dequeue it and see if it's value is greater than or equal to the current node's value. If so then the BST is not valid so return false.

    4. Put the current node in the queue.

    5. Recursively traverse the right subtree. Return false if any nodes are invalid.

    6. We made it to the end with no invalid nodes! Return true.

    Alternatively, instead of using a queue you could keep track of the previously traversed node in the in-order traversal. Note that you must explicitly pass the previous node by reference.

    public class Solution 
    {
        public bool IsValidBST(TreeNode root) 
        {
            TreeNode node = null;
            return IsValidBST(root, ref node);
        }
        
        private bool IsValidBST(TreeNode node, ref TreeNode previous)
        {
            if (node == null) return true;
            if (!IsValidBST(node.left, ref previous)) return false;
            if (previous != null && previous.val >= node.val) return false;
            previous = node;
            if (!IsValidBST(node.right, ref previous)) return false;
            return true;
        }
    }

Log in to reply
 

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