Easy Top Down && Bottom Up(beat 89.35%) Solutions in JAVA


  • 6

    Top Down Solution, which is O(n^2) time complexity

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        if (root.left == null && root.right == null) return true;
        int left = depth(root.left);
        int right = depth(root.right);
        return Math.abs(left-right) <=1 && isBalanced(root.left) && isBalanced(root.right);
    }
    public int depth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return Math.max(depth(root.left),depth(root.right))+1;
    }
    

    Bottom Up Solution, which is O(n) time complexity

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int depth = depth(root);
        if (depth == -1) return false;
        else return true;
    }
    private int depth(TreeNode root) {
        if (root == null) return 0;
        int left = depth(root.left);
        int right = depth(root.right);
        if (left == -1 || right == -1 || Math.abs(left-right) > 1) return -1;
        return Math.max(left,right)+1;
    }

Log in to reply
 

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