algorithm - 给定一棵二叉树，找到所有根到叶的路径

Question

给定一棵二叉树，问题是找到所有根到叶的路径。我们通过以列表的形式传递路径并在我们一碰到叶子就将其添加到我们的结果中来了解该算法。

我的问题存储所有路径消耗多少空间。我的直觉是，每条路径都会消耗树高的内存顺序(O(h))，如果我们的完整二叉树中有 2*n - 1 个节点，那么有 n 个叶子，每个叶子对应一条路径因此假设树是高度平衡的，空间复杂度将是 O(n*log(n))。我的分析正确吗？

Answer 1

您的推理是正确的，但可以更精确。平衡二叉树不一定是 full binary tree .

---

令 N(h) 为高度为 h 时的路径数。那么 N(h) ≤ 2 N(h - 1) 这是因为，给定一棵高度为 h 的树，每个子树的高度至多为 h-1。所以

N(h) = O(2^h)。

---

现在我们需要绑定(bind)h。由于 h 出现在指数中，因此仅找到其增长顺序是不够的。更准确地说，它是 known那个

n ≥ 2^h - 1

所以

h ≤ log(n + 1)

将这个插入到我们之前的内容中

N(h) = O(2^{log(n + 1)}) = O(n)。

---

正如您所写，内存是路径上节点的每条路径的总和。每条路径上的节点总和最多为 log(n + 1)。结合以上所有得到 O(n log(n))。