二叉树的锯齿形层次遍历

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

例如:
给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下:

[
[3],
[20,9],
[15,7]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal

解题思路:二叉树的层次遍历,可以直接使用BFS进行搜索,然后根据层数偶翻奇不翻即可

# 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: TreeNode) -> List[List[int]]:
        if not root:
            return []
        stack = [root]
        deep = 1
        ans = []
        while stack:
            deep += 1
            layer = list()
            next_stack = list()
            for node in stack:
                layer.append(node.val)
                if node.left:
                    next_stack.append(node.left)
                if node.right:
                    next_stack.append(node.right)
            stack = next_stack
            if deep % 2:
                ans.append(layer[::-1])
            else:
                ans.append(layer)
        return ans
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00