1ms Java solution, O(n) time and O(1) space, using Integer object and null pointer


  • 17
    Y
    public class Solution {
        public boolean isValidBST(TreeNode root) {
            return isValidBSTHelper(root, null, null);
        }
    
        private boolean isValidBSTHelper(TreeNode root, Integer leftBound, Integer rightBound) {
            // recursively pass left and right bounds from higher level to lower level
            if (root == null) {
                return true;
            }
            if (leftBound != null && root.val <= leftBound || rightBound != null && root.val >= rightBound) {
                return false;
            }
            return isValidBSTHelper(root.left, leftBound, root.val) && isValidBSTHelper(root.right, root.val, rightBound);
        }
    }

  • 1

    If you using recursion, it would less likely to be O(1) space.


Log in to reply
 

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