博客

题目链接

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

题目描述

给定一棵二叉树，返回树的zigzag层次遍历结果（当前层从左向右遍历，下一层就从右向左遍历……）。

示例

给定二叉树：

   3
   / \
  9  20
    /  \
   15   7

返回的zigzag层次遍历结果为：

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

解决思路一

这道题类似【leetcode-Python】-Tree-102. Binary Tree Level Order Traversal。第一种解决思路是BFS迭代，由一个变量判断当前层是从左向右遍历还是从右向左遍历。

列表反向可以由list.reverse()实现，需要注意的是这个语句没有返回值，直接对list中列表元素反转。此外还可以由[::1]和[::-1]分别实现正向和反向。

# 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]]:
        result = []
        if not root:
            return result
        level = [root]
        int_level = 0 #偶数从左往右，奇数从右往左
        while(len(level) != 0):
            tmp = [node.val for node in level]
            LRPairs = [(node.left,node.right) for node in level]
            level = [node for pair in LRPairs for node in pair if node]
            if int_level % 2 == 0:
                result.append(tmp)
            else:#奇数
                tmp.reverse() #list.reverse()直接list被反转,不返回值
                result.append(tmp)
            int_level += 1 
        return result

时间复杂度和空间复杂度

 时间复杂度为O(n),空间复杂度为O(n).

(list.reverse()的时间复杂度为O(n), list[::-1]实现反转的时间复杂度为O(k))

解决思路二

第二种思路为DFS递归。同样类似【leetcode-Python】-Tree-102. Binary Tree Level Order Traversal，在原来层次遍历的基础上增加对当前遍历到的二叉树遍历层数的奇偶判断。如果需要从右往左遍历，那么插入时用deque.appendleft()能够保证常数复杂度下的高效插入。

# 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
from collections import deque
class Solution:
    def dfs(self,result,level,root):
        if not root: #递归结束
            return
        if len(result) == level:
            result.append(deque([]))
        if level % 2 == 0: #偶数层从左往右
            result[level].append(root.val)
        else:
            result[level].appendleft(root.val) 
        self.dfs(result,level+1,root.left)
        self.dfs(result,level+1,root.right)
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if not root:
            return result
        level = 0
        self.dfs(result,level,root)
        return result

时间复杂度和空间复杂度

时间复杂度为O(n),空间复杂度为O(n).