思路：
层次遍历：
下面这中方式复杂化了：变动了结点
# 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]]
"""
if root is None:
return []
results = []
queue = [root]
count = 1 # 记录层数
while queue:
count += 1
result = [] # 记录下一层的值
now_queue = []
nums = len(queue) # 记录每层的结点个数
for i in range(nums):
node = queue.pop(0)
result.append(node.val)
left = node.left
right = node.right
if count % 2 == 0:
if left:
now_queue.append(left)
if right:
now_queue.append(right)
else:
if right:
now_queue.append(right)
if left:
now_queue.append(left)
queue = now_queue[-1::-1]
results.append(result)
return results
其实很简单，就是层次遍历，只不过是将奇数层的值翻转一下！！！
class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
queue = [root]
results = []
count = 0
while queue:
count += 1
nums = len(queue)
result = []
for i in range(nums):
node = queue.pop(0)
left = node.left
result.append(node.val)
right = node.right
if left:
queue.append(left)
if right:
queue.append(right)
if count % 2 == 0:
result = result[::-1]
results.append(result)
return results
