My Java Answer is accepted, but what is my time complexity?


  • 0
    T
    public class Solution {
        public boolean isBalanced(TreeNode root) {
        	if(root==null){
        		return true;
        	}
            if(Math.abs(maxDepth(root.left)-maxDepth(root.right))>1){
            	return false;
            }
            return (isBalanced(root.left))&&(isBalanced(root.right));	
            
        }
        public int maxDepth(TreeNode root) {
            if(root == null){
                return 0;
            }
            return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
        }
    }

  • 0
    L

    I think it's o(n^2). For each node, your code will go through every child nodes of this node. The worst case is the tree is a perfect binary tree. So the time will be
    n-1/root node/ + (n-3)*2 /second level/ + (n-7)*4/third level/ + (n-2^k+1)*2^k/kth level/


Log in to reply
 

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