【LeetCode每天一题】Binary Tree Zigzag Level Order Traversal(二叉树的之字形遍历)
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
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
思路
对于二叉树的之字形遍历，我们可以使用像之前对二叉树进行层次遍历时一样，只不过这里对每一层节点在添加子节点时的顺序有要求，当为基数层时，我们在添加节点时选择先添加左边的子节点，在添加右边的子节点。 当为偶数层时，我们应该先添加右边的子节点，在添加左边的子节点。然后遍历完毕之后在将该层节点的遍历结果添加到最终列表中。
解决代码
1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 # def __init__(self, x): 4 # self.val = x 5 # self.left = None 6 # self.right = None 7 8 class Solution(object): 9 def zigzagLevelOrder(self, root): 10 """ 11 :type root: TreeNode 12 :rtype: List[List[int]] 13 """ 14 if not root: 15 return [] 16 17 res, index = [], 0 # 结果列表 和 当前层数变量 18 stack = [root] # 使用辅助栈 19 while stack: 20 tem_stack, count = [], len(stack) # 申请一个空列表来存储当前层的子节点， count表示当前层中的节点个数 21 level, index = [], index + 1 # level 表示存储当前层的节点值的遍历顺序， 22 for _ in range(count): # 当前层有多少个节点就遍历多少次 23 tem = stack.pop() # 弹出顶部元素 24 if index % 2 == 1: # 判断当前层，然后选择不同的子节点添加规则。 25 if tem.left: # 奇数层先添加左节点，在添加右节点 26 tem_stack.append(tem.left) 27 if tem.right: 28 tem_stack.append(tem.right) 29 else: # 偶数层先添加右节点在添加左节点。 30 if tem.right: 31 tem_stack.append(tem.right) 32 if tem.left: 33 tem_stack.append(tem.left) 34 35 level.append(tem.val) # 添加当前节点的值 36 stack = tem_stack # 当前层遍历结束之后，将tem_stack赋值给stack.（tem_stack表示下一层子节点的排列顺序） 37 res.append(level) # 当前层的遍历结果添加进去 38 return res 39
更多精彩
