CBTCheck.java

public class CBTCheck {
    private int[] walk(TreeNode root) {
        if (root == null) { return new int[]{0, 0, 1}; } // min, max, valid
        int[] left = walk(root.left);
        int[] right = walk(root.right);
        int valid = left[2] & right[2];
        if (right[1] > left[1]) {
            valid = 0;
        } else if (right[1] + 1 < left[1]) {
            valid = 0;
        } else if (left[0] != left[1] && (right[0] != right[1] || right[1] != left[0])) {
            valid = 0;
        }
        return new int[]{1 + Math.min(left[0], right[0]), 1 + Math.max(left[1], right[1]), valid};
    }

    public boolean isCompleteTree(TreeNode root) {
        int[] result = walk(root);
        return result[2] == 1 ? true : false;
    }
}