P234. 二叉树中的所有路径

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 是树上的节点数量。