Why my code is Time Limit Exceeded (leetcode104)

Question

I am solving some exercises at leetcode 104

Desciption : Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Here is my solution

  public int maxDepth(TreeNode root) {
      if(root ==null ) {
         return 0 ;
      }   
      return ( maxDepth(root.left)+1) > (maxDepth(root.right)+1 ) ?
             (maxDepth(root.left)+1):(maxDepth(root.right)+1);
  }

But it throws Time Limit Exceeded .

Then I change it to this ,it runs well and accepted

 public int maxDepth(TreeNode root) {
          if(root ==null ) {
             return 0 ;
          }
          int left  = maxDepth(root.left)+1;
          int right = maxDepth(root.right) +1 ;
          return left > right ? left :right ; 
        }

But I don't think they have any differences . Please help me to understad where I had made the mistake . Thanks for your guide, cheers!

Answer 1

probably four method call

(maxDepth(root.left)+1) > (maxDepth(root.right)+1 ) ?
(maxDepth(root.left)+1):(maxDepth(root.right)+1)

Here you are calling the maxDepth method 4 times which is not efficient.

Calculations for root.left and root.right are duplicated recursion calls which are not necessary. Try to think and optimize your solution by reducing the number of method calls and this will make your code execute within much faster.

Your second code snippet involves only 2 recursive method calls, making it a better performing solution.

You can even use a much simpler solution:

if (root == null) {
    return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;