python - 打印二叉树的所有路径

Question

给定一个完整的二叉树（每个节点都有 1 个左子节点和 1 个右子节点），编写一个算法来打印所有从根到叶的路径。

这是Python中的递归算法：

def print_tree(root):
  dfs(root, '')

def dfs(root, path):
  path += root.value
  if not root.right and not root.left:
     print path
     return
  if root.left:    
     dfs(root.left,path)
  if root.right:
     dfs(root.right,path)

空间复杂度的粗略分析是：栈帧上的O(log(N))（递归调用的最大数量是树的深度）堆上的O(log(N))（字符串构造的最大数量也是树的深度，给定的路径是一个在 python 中不可变的字符串）。

更难的问题是：描述叶节点的总内存使用量。

因此，在叶节点处，我们将在调用堆栈上有 log(N) 个函数指针。但是存在多少“副本”或内存分配path？我认为也有 log(N) 这样的副本，因为在每个调用函数返回之前不会对路径进行垃圾收集。

因此，在叶节点，我们有 log(N) + log(N) 的总内存复杂度。那准确吗？

标签： pythonmemory