https://algocasts.io/episodes/4rpaNoWZ
StringBuilder 版本的时间复杂度分析
StringBuilder 版本和 String 版本不同,在构建路径时不会拷贝所有的字符,而是用 O(1)
的时间追加字符即可。也正因如此,在最后把一条路径存储到 result 中时,我们需要把 StringBuilder 中的字符数组(char[] value
)拷贝一份作为 String(代码:path.toString()),时间复杂度是 O(lengthOfPath)
。
因此,总的时间复杂度则是:O(lengthOfPath) x numOfPath
,最坏情况是去处理一棵满二叉树。这个时候路径数量(也就是叶子节点的数量)是 (n+1)/2
,因此找出所有路径的复杂度是 O(n)
。而每条路径的长度是 O(log(n))
,保存到 result 时需要做一次拷贝,时间复杂度是 O(log(n))
。因此,总的时间复杂度是 O(n*log(n))。
对于空间复杂度,最坏情况下是去处理一棵斜树,这时树的高度是 n,最大递归深度是 n,因此递归使用的辅助栈空间是 O(n)
;StringBuilder 需要使用的空间是路径的最大长度,也是 O(n)
。因此,总的空间复杂度是 O(n)。
使用相同的分析方法,可以很容易分析出另一种极端情况的时间复杂度和空间复杂度(并非最坏情况。由于时间复杂度和空间复杂度一般讨论的是最坏情况,因此我们使用上面的结果):
- 对于斜树,时间复杂度是
O(lengthOfPath) x numOfPath = O(n) x 1 = O(n)
- 对于满二叉树,树高为
O(log(n))
,路径的最大长度是O(log(n))
,因此空间复杂度是O(log(n))
注意:n 是树上的节点数量。