An easy understand Divide&Conquer Solution


  • 0
    W
    public class Solution {
        public boolean isValidBST(TreeNode root) {
            return isValid(root)[2]==1;
        }
        public long[] isValid(TreeNode root){
            if(root==null){
                long[] ans = {(long)Integer.MIN_VALUE-1, (long)Integer.MAX_VALUE+1, 1};
                return ans;
            }
            long[] left = isValid(root.left);
            long[] right = isValid(root.right);
            long[] ans = {0,0,1};
            if(left[2]==0||right[2]==0||(long)root.val>=right[1]||(long)root.val<=left[0]){
                ans[2] = 0;
                return ans;
            }
            ans[0] = Math.max((long)root.val, Math.max(left[0], right[0]));
            ans[1] = Math.min((long)root.val, Math.min(left[1], right[1]));
            return ans;
        }
    }
    

Log in to reply
 

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