时间戳

首页 > 解决方案 > 为什么我的代码超过了时间限制 (leetcode104)

java - 为什么我的代码超过了时间限制 (leetcode104)

问题描述

我正在leetcode 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 ; 
        }

但我不认为他们有任何区别。请帮助我了解我在哪里犯了错误。谢谢你的指导，加油！

标签： javarecursiontime-complexityspace-complexity

解决方案

大概有四种方法调用

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

在这里，您调用了 4 次 maxDepth 方法，效率不高。

root.left 和 root.right 的计算是不必要的重复递归调用。尝试通过减少方法调用的数量来思考和优化您的解决方案，这将使您的代码执行得更快。

您的第二个代码片段仅涉及 2 个递归方法调用，使其成为性能更好的解决方案。

您甚至可以使用更简单的解决方案：

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

推荐阅读