LeetCode Algorithm 103. 二叉树的锯齿形层序遍历

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

Ideas

首先得理解二叉树的层序遍历，它类似于广度优先搜索，在当前层搜索的时候，遍历到的每一个节点都要把它的所有孩子节点都添加到队列中。

然后我们要锯齿形遍历，可以定义一个order变量，如果为True表示从左往右遍历，如果为False表示从右往左遍历，每次遍历完取反。

Code Python

from collections import deque from typing import List # Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val
		self.left = left
		self.right = right class Solution: def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] queue = deque() queue.append(root) order, ans = True, [] while queue: level = [] for i in range(len(queue)): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) ans.append(level if order else level[::-1]) order = not order return ans