binary-tree - 二叉树上 BFS 和 DFS 的时间复杂度：为什么是 O(n)？

Question

图上 BFS 或 DFS 的时间复杂度为 O(V+E)，因为我们遍历了图的所有节点和边。（我明白了）但是对于二叉树，BFS 和 DFS 的时间复杂度是 O(V)... 为什么会这样？

我假设是因为以下原因：O（V + E）= O（V + V-1）= O（2V）= O（V）。这是正确的推理吗？如果没有，将不胜感激直观的解释。谢谢

标签： binary-treedepth-first-searchtraversalbreadth-first-searchtree-traversal

Answer 1

所有的树都有n - 1边，n即节点的数量。时间复杂度在技术上仍然是 O(V + E)，但这等于 O(n + (n-1)) = O(n)。