LeetCode 103. Binary Tree Zigzag Level Order Traversal.jpg
LeetCode 103. Binary Tree Zigzag Level Order Traversal
Description
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
[
[3],
[20,9],
[15,7]
]
描述
给定二叉树，返回其节点值的Z字形级别遍历。 （即，从左到右，然后从右到左进行下一级别并在之间交替）。
思路
- 此题目同上一题102题思路完全一致，我们只需要加一个判断来确定当前层是否需要反转即可.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2018-12-29 18:55:05
# @Last Modified by: 何睿
# @Last Modified time: 2018-12-29 19:20:04
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
# 如果子树为空，则直接返回空
if not root:
return []
# 当前遍历层的所有节点，下一层将遍历的所有节点
currnode, nextnode, res = [root], [], []
# 数组的起始位置，数组的结束位置，当前层数的所有节点个数
start, end, count = 0, 0, 1
# 循环条件，只有当前层还有节点需要遍历才执行
reverse = False
while currnode:
# 索引开始地址，索引结束地址
start, end = 0, count
# 当前层所有节点的值，count重置为0
level, count = [], 0
for i in range(start, end):
# 如果当前节点有左节点
if currnode[i].left:
# 左节点将在下一层遍历，放入nextnode数组
nextnode.append(currnode[i].left)
# 下一层个数自增一次
count += 1
# 如果当前节点有右节点
if currnode[i].right:
# 右节点将在下一层遍历，放入nextnode数组
nextnode.append(currnode[i].right)
# 下一层个数自增一次
count += 1
# 存储当前节点的值
level.append(currnode[i].val)
# 结果数组存储当前层的所有值
# 如果需要反转，则对结果进行反转
if reverse:
level.reverse()
# 下次不需要反转，重置为False
reverse = False
elif not reverse:
reverse = True
res.append(level)
# currnode置为下一层，nextnode重置为空
currnode, nextnode = nextnode, []
return res
- 以下用python的队列实现了一遍
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2018-12-29 18:55:05
# @Last Modified by: 何睿
# @Last Modified time: 2018-12-29 19:20:04
# Definition for a binary tree node.
from collections import deque
class Solution:
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
# 使用队列实现
if not root:
return []
# 是否需要反转，存储结果，队列
reverse, res, queue = False, [], deque()
queue.append(root)
# 循环条件：队列中还有节点
while queue:
nums, level = len(queue), []
# 遍历当前层的所有节点
for _ in range(0, nums):
current = queue.popleft()
# 左子树
if current.left:
queue.append(current.left)
# 右子树
if current.right:
queue.append(current.right)
level.append(current.val)
# 是否需要反转
if reverse:
level.reverse()
reverse = False
elif not reverse:
reverse = True
res.append(level)
return res
