求二叉树锯齿形层序遍历实现代码的时间复杂度

嘿，针对你这道LeetCode的二叉树锯齿形层序遍历题，我来帮你拆解时间复杂度的问题～

首先，不管你最终是用队列+奇偶层反转的实现思路，还是用双栈交替处理的方式，这道题的时间复杂度都是O(n)，其中n是二叉树的节点总数。具体原因如下：

核心原因拆解 #

• 我们必须遍历二叉树的每一个节点恰好一次：不管是把节点加入队列/栈，还是读取节点的值存入结果数组，每个节点只会被处理一次，这部分的时间开销是线性的O(n)。
• 如果用队列+反转的方式：假设树有k层，最多有⌈k/2⌉层需要执行反转操作。但最坏情况下（比如完全二叉树），需要反转的层的节点总数加起来最多是n/2，而反转一个长度为m的数组的时间是O(m)，所有反转操作的总时间加起来还是O(n)——因为所有节点只会被反转一次，不会重复消耗时间。
• 如果用双栈交替的方式：每个节点入栈和出栈各一次，没有额外的反转操作，总操作次数依然是O(n)，不会产生额外的时间消耗。

额外补充：空间复杂度 #

顺便提一句空间复杂度，不管哪种实现方式，最坏情况下（比如满二叉树的最后一层，节点数占总数的一半）需要存储最多⌈n/2⌉个节点，所以空间复杂度也是O(n)。

拿你给出的示例树来说：

3
   / \
  9  20
    /  \
   15   7

总共有5个节点，每个节点都被访问一次，反转操作只针对第二层的[9,20]，耗时O(2)，总时间就是O(5)，完全符合线性复杂度的结论。

总结一下：不管你最终采用哪种实现，这道题的时间复杂度都是线性的O(n)，因为每个节点只会被处理常数次，没有嵌套循环之类的操作会带来更高的时间开销。

内容的提问来源于stack exchange，提问作者P.K.