Leetcode 求二叉树的最大深度问题，为什么这两种解法耗时会相差两倍？
Deardrops · deardrops · 2018-12-08 12:25:18 +08:00 · 3880 次点击这是一个创建于 2210 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目：给定一个二叉树，找出其最大深度。 语言：Golang
解法①：
// 16ms, beat 12.46%
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
leftDepth := maxDepth(root.Left)
rightDepth := maxDepth(root.Right)
if leftDepth > rightDepth {
return leftDepth + 1
} else {
return rightDepth + 1
}
}
解法②：
// 8ms, beat 100%
func maxDepth(root *TreeNode) int {
if root != nil {
leftDepth := maxDepth(root.Left)
rightDepth := maxDepth(root.Right)
if leftDepth > rightDepth {
return 1+leftDepth
}
return 1+rightDepth
}
return 0
}
实际提交到 leetcode 上，前者耗时 16ms，后者耗时 8ms。
初学 Golang，请问这两段代码为什么执行时间会差两倍？
14 条回复 • 2018-12-08 19:02:02 +08:00
 |
1
Jex 2018-12-08 12:33:47 +08:00  4
要先学会正确的性能测试方法
|
 |
2
notreami 2018-12-08 12:47:57 +08:00 1
第一个解法，我这边运行是 8ms
做第一个题的时候，就发现同样的代码，执行结果耗时有差异，猜测可能是 gc，或者资源排队等问题。 |
 |
3
lhx2008 2018-12-08 12:55:51 +08:00 via Android 1
leetcode 的隔离很差，波动大也很正常
|
 |
5
kaitian521 2018-12-08 13:20:47 +08:00
c
|
|
6
kaitian521 2018-12-08 13:22:16 +08:00
试一下 maxDepth(root.Left)>maxDepth(root.Right)? 1+maxDepth(root.Left): 1+maxDepth(root.Right);
|
 |
7
msg7086 2018-12-08 13:23:07 +08:00
你自己拿个秒表，掐两次，然后想想为什么其中一次会是另一次时间的两三倍，就知道原因了。
|
 |
8
QK8wAUi0yXBY1pT7 2018-12-08 13:39:30 +08:00
你自己同一个解法不同时间再提交，也可能差两倍
|
 |
10
onepunch 2018-12-08 15:35:07 +08:00
运行一万次的时间 / 10000 是每次运行的时间 [手动狗头]
|
 |
11
zzj0311 2018-12-08 16:28:47 +08:00 via Android
leetcode 时间并不能作为性能测试的依据，特别是几个 ms 的那种
|
 |
12
gqw121314 2018-12-08 17:18:23 +08:00
我相同的代码重复提交了 3 次，每次时间都不一样。。。
|
 |
13
akira 2018-12-08 18:34:35 +08:00
以 ms 为单位的性能统计，±50ms 很正常的
|
 |
14
bubuhere 2018-12-08 19:02:02 +08:00 via iPhone
leetcode 给出的时间没有太大参考性
|
Select Language