time-complexity - 二叉树遍历的复杂性

Question

数据结构中二叉树的中序、后序、先序遍历的时间复杂度是多少？是 O(n) 还是 O(log n) 还是 O(n^2)？

Answer 1

中序、前序和后序遍历都是深度优先遍历。

对于图，深度优先遍历的复杂度为 O(n + m)，其中 n 是节点数，m 是边数。

由于二叉树也是图，因此这里同样适用。每个深度优先遍历的复杂度都是 O(n+m)。

由于在二叉树的情况下，源自节点的边数限制为 2，因此二叉树中的总边数最大为 n-1，其中 n 是节点总数。

复杂度变为 O(n + n-1)，即 O(n)。