5 Java Accepted Solutions


  • 0
    J

    Solution 1: recursive, record the previous value, CONS: use global variable

    class Solution {
        Long prev = Long.MIN_VALUE;
        boolean res = true;
        public boolean isValidBST(TreeNode root) {
            if (root == null) {
                return res;
            }
            helper(root);
            return res;
        }
        private void helper(TreeNode root) {
            if (root == null) {
                return;
            }
            helper(root.left);
            if (prev >= root.val) {
                res = false;
                return;
            }
            prev = (long) root.val;
            helper(root.right);
        }
    }
    

    Solution 2: root.val has to be in the range of maximum in left subtree and minimum in right subtree, recursive

    class Solution {
        public boolean isValidBST(TreeNode root) {
            return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
        }
        
        public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
            if (root == null) return true;
            if (root.val >= maxVal || root.val <= minVal) return false;
            return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
        }
    }
    

    Solution 3: root.val has to be in the range, do not use global variable, worse than solution 2

    class Solution {
        public boolean isValidBST(TreeNode root) {
            if (root == null) {
                return true;
            }
            ResultType res = helper(root);
            return res.isValid;
        }
        private ResultType helper(TreeNode root) {
            if (root == null) {
                return new ResultType(true, Long.MAX_VALUE, Long.MIN_VALUE);
            }
            if (root.left == null && root.right == null) {
                return new ResultType(true, root.val, root.val);
            }
            ResultType left = helper(root.left);
            ResultType right = helper(root.right);
            if (left.isValid && right.isValid && left.max < root.val && root.val < right.min) {
                return new ResultType(true, Math.min(root.val, left.min), Math.max(root.val, right.max));
            } else {
                return new ResultType(false, Math.min(root.val, Math.min(left.min, right.min)), Math.max(root.val, Math.max(left.max, right.max)));
            }
        }
    }
    class ResultType {
        boolean isValid;
        long min;
        long max;
        ResultType(boolean isValid, long min, long max) {
            this.isValid = isValid;
            this.min = min;
            this.max = max;
        }
    }
    

    Solution 4: iterative inorder traversal, using stack

    class Solution {
        public boolean isValidBST(TreeNode root) {
            if (root == null) {
                return true;
            }
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode cur = root;
            long prev = Long.MIN_VALUE;
            while (!stack.isEmpty() || cur != null) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.pop();
                if (cur.val <= prev) {
                    return false;
                }
                prev = cur.val;
                cur = cur.right;
            }
            return true;
        }
    }
    

    Solution 5: iterative inorder traversal, Morris Traversal, space: O(1)

    class Solution {
        public boolean isValidBST(TreeNode root) {
            if (root == null) {
                return true;
            }
            TreeNode cur = root;
            TreeNode pre = null;
            long prev = Long.MIN_VALUE;
            while (cur != null) {
                if (cur.left == null) {
                    if (cur.val <= prev) {
                        return false;
                    }
                    prev = cur.val;
                    cur = cur.right;
                } else {
                    pre = cur.left;
                    while (pre.right != null) {
                        pre = pre.right;
                    }
                    pre.right = cur;
                    TreeNode temp = cur;
                    cur = cur.left;
                    temp.left = null;
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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