103_二叉树的锯齿形层序遍历

类型：树

• 103. 二叉树的锯齿形层序遍历 💛

  https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

  ❓ 给定一个二叉树，返回其节点值的锯齿形层序遍历。（第一层从左往右，第二层从右往左……）。

  💡 BFS

  我们用一个变量来记录当前是从左往右还是从右往左。我们将同层结点存入队列，由于方向是交替切换的，正序取反后得到反序，反序取反后又回到了正序。

  class Solution:
      def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
          if not root:
              return []
          direction = 1
          ans = []
          queue = [root]
          while queue:
              newQueue = []
              row = []
              for i in range(len(queue) - 1, -1, -1):
                  node = queue[i]
                  row.append(node.val)
                  if direction == -1:
                      if node.right: newQueue.append(node.right)
                      if node.left: newQueue.append(node.left)
                  else:
                      if node.left: newQueue.append(node.left)
                      if node.right: newQueue.append(node.right)
              direction *= -1
              ans.append(row[:])
              queue = newQueue
          return ans

  时间复杂度：O(n)，空间复杂度：O(1)