Почему мой код превышен по времени (leetcode104)

Question

Я решаю некоторые упражнения на Леткод 104

Описание: По заданному бинарному дереву найдите его максимальную глубину. Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего конечного узла.

Вот мое решение

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

Но это бросает Time Limit Exceeded.

Затем я изменяю это на это, он работает хорошо и принял

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

Но я не думаю, что у них есть какие-либо различия. Пожалуйста, помогите мне понять, где я совершил ошибку. Спасибо за ваше руководство, ура!

Answer 1

возможно четыре вызова метода

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

Здесь вы вызываете метод maxDepth 4 раза, что неэффективно.

Расчеты для root.left и root.right - это дублированные рекурсивные вызовы, которые не нужны. Постарайтесь продумать и оптимизировать свое решение, сократив количество вызовов методов, и это сделает ваш код гораздо быстрее.

Ваш второй фрагмент кода включает только 2 рекурсивных вызова метода, что делает его более эффективным решением.

Вы даже можете использовать гораздо более простое решение:

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