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


  • 7

    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;
    }

  • 0
    N

    Hi,
    could you tell me why top - down solution is o(n^2) time complexity ?
    my understanding is worst case would be linked list
    then f(n) = o(n) + f(n-1) = o(n^2).
    Please confirm
    thanks.


Log in to reply
 

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