MY simple java recursion method. Can solve many questions in leetcode like this.


  • 0
    G

    public class Solution {

    public boolean isValidBST(TreeNode root) {
        if(root == null){ return true;}
        int[] minMax = findTreeMinMax(root);
        return minMax[0] <= minMax[1];
    }
    

    // The returned array result[] first element is min the tree rooted at root, and the second element is the max. If result[0] >= result[1], it means it is not a BST.

    public int[] findTreeMinMax(TreeNode root) {
        if(root.left == null && root.right == null){
            return new int[]{root.val, root.val};
        }
        int[] leftResult = new int[2];
        int[] rightResult = new int[2];;
        if(root.left != null){
            leftResult = findTreeMinMax(root.left);
            if(leftResult[0] > leftResult[1] || leftResult[1] >= root.val){
                return new int[]{2,1};// means not a BST, because the first element is supposed to smaller than the second one
            }
        }
        if(root.right != null){
            rightResult = findTreeMinMax(root.right);
            if(rightResult[0] > rightResult[1] || rightResult[0] <= root.val){
                return new int[]{2,1};
            }
        }
        if(root.left == null){
            return new int[]{root.val, rightResult[1]};
        }
        if(root.right == null){
            return new int[]{leftResult[0], root.val};
        }
        return new int[]{leftResult[0], rightResult[1]};
    }
    

    }


Log in to reply
 

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