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

Difficulty
Medium
Tags
二叉树
二叉树层次遍历
URL
https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
Star
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层序遍历如下：
[
  [3],
  [20,9],
  [15,7]
]

法1：BFS

思路
可以发现，输出结果 和 标准层次遍历输出的区别只在列表中的子列表顺序一正一反。
题解
所以添加temp_list到result时按照一正一反的顺序即可。本程序中采用添加一个flag标志位来实现一正一反的输入
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if root is None:
            return result
        queue = []
        queue.append(root)
        flag = 1 # 用来控制正序 逆序的标志 
        while len(queue) > 0:
            temp_len = len(queue)
            temp_list = []
            while temp_len > 0:
                temp_node = queue.pop(0)
                temp_list.append(temp_node.val)
                temp_len -= 1

                if temp_node.left:
                    queue.append(temp_node.left)
                if temp_node.right:
                    queue.append(temp_node.right)
						# 一正一反序的添加到result
            if flag == 1:
                result.append(temp_list)
            elif flag == -1:
                result.append(temp_list[::-1])
            flag = flag * -1
        return result

法2 DFS

思路
同
🥎
102. 二叉树的层序遍历 区别在于，每一层中插入的顺序一正一反，所以引入了一个变量flag 来判断是头插还是尾插。
题解
# 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]]:
        res = []
        self.dfs(node=root, depth=0, result=res, flag=1)
        return res
    def dfs(self, node, depth, result, flag):
        '''用flag 来判断是正序插入还是反序插入
        '''
        if node is None:
            return 
            
        if len(result) == depth:
            result.append([])
        
        if flag == 1:
            result[depth].append(node.val)
        else:
            result[depth].insert(0, node.val)
        
        self.dfs(node.left, depth+1, result, flag*-1)
        self.dfs(node.right, depth+1, result,flag*-1)