M-103. Binary Tree Zigzag Level Order Traversal

Loading...LeetCode

# O(n), O(n). BFS.
# right_to_left决定当前层pop的时候, 是从左边还是右边pop, 如果需要从当前层得到的结果(即cur_res)
# 是从左往右的, 那么right_to_left就是False, 反之, 是True. 

# 1. 我们从一个从左往右的层开始看, 我们出的时候, popleft, 并把pop出来的节点加入cur_res, 并把
# 每一个pop出来的节点的left和right按顺序append入deque.

# 2. 于是这样下一个就是从右往左的层, 我们处理这层的时候, popright(即pop), 再把pop出来的节点
# 加入cur_res, 并把每一个pop出来的节点的right和left按顺序appendleft入deque

# 3. 我们发现我们deque里面的节点总是从左往右的, 区别只是, 我们在处理从左往右层的时候, 我们把它当
# queue用, 并且把这些popleft出来的节点的子节点按从左往右地append进来; 而我们在处理从右往左层
# 的时候, 我们把它当stack用, 并且把这些pop出来的节点的子节点按从右往左地appendleft进来.

# 好神奇..

import collections
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        deq = collections.deque()
        if not root:
            return []
        res = []
        deq.append(root)
        right_to_left = False
        
        while deq:
            length = len(deq)
            cur_res = []
            for _ in range(length):
                if not right_to_left:
                    node = deq.popleft() 
                    if node.left: deq.append(node.left)
                    if node.right: deq.append(node.right)
                    cur_res.append(node.val)
                else:
                    node = deq.pop()
                    if node.right: deq.appendleft(node.right)
                    if node.left: deq.appendleft(node.left)
                    cur_res.append(node.val)
            right_to_left = not right_to_left
            res.append(cur_res)    
        
        return res