LeetCode 103. 二叉树的锯齿形层次遍历（双栈层次遍历）

Description

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如： 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回锯齿形层次遍历如下： [ [3], [20,9], [15,7] ]

Solution

同剑指offer之字打印二叉树

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]: if not root: return [] cur = [root] ans = [] cnt = 0 while cur: tmpans = [] next_ = [] while cur: while cur: node = cur.pop() tmpans.append(node.val) if (cnt & 1) == 0: if node.left: next_.append(node.left) if node.right: next_.append(node.right) else: if node.right: next_.append(node.right) if node.left: next_.append(node.left) cur = next_ ans.append(tmpans) cnt += 1 return ans