我正在 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);
}
但它抛出超过时间限制
。
然后我把它改成这样,它运行良好并被接受
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 ;
}
但我不认为它们有任何区别。请帮助我了解我在哪里犯了错误。 感谢您的指导,干杯!
最佳答案
可能有四个方法调用
(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;
关于java - 为什么我的代码超出了时间限制(leetcode 104),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50206919/