1 ms java recursive solution without passing max and min to next level


  • 1
    B

    these two if statemnt "if(root.left.val >= root.val) { return false;} and if (root.right.val <= root.val) {return false;}" can make sure that parent node's key greater than left child'key and parent node's key less than right child's key ,but can not satisfy that the left subtree of a node contains only nodes with keys less than the node's key and the right subtree of a node contains only nodes with keys greater than the node's key. so i have to find the left subtree's max key and right subtree's min key , make sure that root's key > left subtree's max key and root's key < right subtree's min key.

    public class Solution {
        public boolean isValidBST(TreeNode root) {
            if(root == null) {
                return true;
            }
            if(root.left != null ) {
                if(root.left.val >= root.val) {
                    return false;
                }
                TreeNode rightmost = root.left;
                while(rightmost.right != null) {
                    rightmost = rightmost.right;
                }
                if (rightmost.val >= root.val) {
                    return false;
                }
            }
            if(root.right != null) {
                if (root.right.val <= root.val) {
                    return false;
                }
                TreeNode leftmost = root.right;
                while(leftmost.left != null) {
                    leftmost = leftmost.left;
                }
                if (leftmost.val <= root.val) {
                    return false;
                }
            }
            return isValidBST(root.left) && isValidBST(root.right);
        }
    }
    

Log in to reply
 

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