103. 二叉树的锯齿形层次遍历 [medium]

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

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

例如：

给定二叉树 [3,9,20,null,null,15,7],

返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

通过次数53,624 | 提交次数98,428

First Try

2020-06-26

问题的重点在于使用BFS的时候如何标记level的信息，其实前几天就做过，但我已经遗忘了，还是花了一点时间才想到同样的方法--把level信息与node节点一起作为tuple存储进队列中。一开始还打算修改node树信息，递归一遍树，把每个节点标记上level信息，但感觉太拙劣了。

看了题解，发现还有其他的思路。一是在BFS的队列中，使用NONE进行一层节点结束的标记，比如最开始只需要用[root, None]既可以成功标记一层信息，接下来每次轮到None的时候，同样把None放进队列里就可以了。这也是一个很巧妙的方法。

其次题解里还可以用DFS实现BFS的遍历，跟我一样把level信息带入递归中，既然父节点level信息已知，子节点level信息就是理所当然，然后在列表中相应位置按照次序插入即可。

# 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]]
        """
        # add level for root
        if not root:
            return []
        queue = [(0,root)] # level直接标记在外部，也可以
        col = []
        while len(queue):
            level, node = queue.pop(0)
            if len(col) < level + 1:
                col.append([])
            if level % 2 == 0:
                col[-1].append(node.val)
            else:
                col[-1].insert(0, node.val)
            if node.left:
                queue.append((level + 1, node.left))
            if node.right:
                queue.append((level + 1, node.right))
        return col

执行用时：8 ms, 在所有 Python 提交中击败了99.73%的用户
内存消耗：13 MB, 在所有 Python 提交中击败了14.29%的用户

103. 二叉树的锯齿形层次遍历 [medium]​

First Try​

103. 二叉树的锯齿形层次遍历 [medium]

First Try