二叉树的锯齿形层次遍历
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:
给定二叉树 [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下:
[
[3],
[20,9],
[15,7]
]
我的想法是把树的每一层存起来,然后 技术层次的结点顺序翻转一下
# 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 root is None:
return []
res = [[root]]
res_int = [[root.val]]
i = 0
while i < len(res):
cur = res[i]
nLayer = []
nLyayer_int = []
for n in cur:
if n.left is not None:
nLayer.append(n.left)
nLyayer_int.append(n.left.val)
if n.right is not None:
nLayer.append(n.right)
nLyayer_int.append(n.right.val)
if nLayer:
res.append(nLayer)
if i % 2 == 0:
nLyayer_int.reverse()
res_int.append(nLyayer_int) i += 1 return res_int