python实现leetcode之103. 二叉树的锯齿形层序遍

解题思路

在每一层处理完的时候调整一下下一层的顺序
从左到右的话是append到队尾
从右到左的话是insert到队头
其他的部分与一般的层次遍历一致

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

代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []

        ans = [[]]
        queue = [(root, 0)]
        level = 0
        left2right = True
        while queue:
            node, lv = queue.pop(0)
            if lv == level:
                if left2right:
                    ans[-1].append(node.val)
                else:
                    ans[-1].insert(0, node.val)
            else:
                level = lv
                left2right = not left2right
                ans.append([node.val])
            if node.left: queue.append((node.left, lv+1))
            if node.right: queue.append((node.right, lv+1))
        return ans