递归遍历树，需要额外的空间吗？

Question

空间复杂度是 o(n) 吗？

Answer 1

是需要额外的空间的，这个得看遍历树的方式是 BFS 还是 DFS，前者是 O(n) 和树的节点数 n 相关，后者是 O(h) 和树的深度 h 相关。