【Leetcode每日笔记】103.二叉树的锯齿形层序遍历(Python)
程序员文章站
2022-05-21 12:25:43
...
题目
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如: 给定二叉树 [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
返回锯齿形层序遍历如下:
[ [3], [20,9], [15,7] ]
解题思路
BFS
利用栈进行正常的层序遍历,即每一次遍历都是从左往右遍历,只不过在记录值的时候加入判断从左往右记录,还是从右往左遍历。
代码
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root :
return []
stack = [root]
n = []
n_val = []
start = -1
ans = [[root.val]]
while stack:
cur = stack.pop(0)
if cur.left:
n.append(cur.left)
n_val.append(cur.left.val)
if cur.right:
n.append(cur.right)
n_val.append(cur.right.val)
if not stack:
stack = n
if start == -1 and n_val:
ans.append(n_val[::-1])
elif n_val:
ans.append(n_val)
n_val = []
n = []
start = -start
return ans
上一篇: jQuery应用中特殊字符处理的问题_jquery
下一篇: 通过正则过滤非法的汉字或字符
推荐阅读
-
leetcode103——二叉树的锯齿形层序遍历——java实现
-
C++实现LeetCode(103.二叉树的之字形层序遍历)
-
【每日一题-leetcode】 102.二叉树的层序遍历
-
【Leetcode每日笔记】103.二叉树的锯齿形层序遍历(Python)
-
Python刷leetcode 103. 二叉树的锯齿形层次遍历
-
Leetcode 103. 二叉树的锯齿形层序遍历 (Java+Python3实现 超详细注释!)
-
LeetCode103:二叉树的锯齿形层序遍历
-
LeetCode - 103. 二叉树的锯齿形层序遍历
-
LeetCode 103. 二叉树的锯齿形层序遍历
-
算法---LeetCode 103. 二叉树的锯齿形层序遍历