欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【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