数据结构中二叉树的中序、后序和前序遍历的时间复杂度是多少？是 O(n) 还是 O(log n) 或 O(n^2)？？
最佳答案
中序、前序和后序遍历是深度优先遍历。
对于图，深度优先遍历的复杂度为 O(n + m)，其中 n 是节点数，m 是边数。
由于二叉树也是图，所以这里同样适用。
每个深度优先遍历的复杂度都是 O(n+m)。
由于在二叉树的情况下可以源自节点的边数限制为 2，因此二叉树中的最大边总数为 n-1，其中 n 是节点总数。
然后复杂度变为 O(n + n-1)，也就是 O(n)。
关于time-complexity - 二叉树遍历的复杂性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4547012/