首页 > itarticle > leetcode_binary tree zigzag level order traversal

leetcode_binary tree zigzag level order traversal

admin 11月 13, 2020 0

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).（按层从左到右->从右到左遍历二叉树）

Example:

1. 递归

与上一题类似，按层遍历，每次都把同层的树节点 Node 组合成一个 List 输入到队列，并在偶数行翻转（变形之后的BFS）。


# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class :
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        results = [[root.val]]
        queue = [[root]]
        
        reverse_flag = 1
        while len(queue) > 0:
            top = queue.pop()
            
            result = []
            level_node = []

            for node in top:
                if node.left:
                    level_node.append(node.left)
                    result.append(node.left.val)
                if node.right:
                    level_node.append(node.right)
                    result.append(node.right.val)
        
            if result:
                if reverse_flag:
                    result.reverse()
    
                reverse_flag = 1 - reverse_flag
                queue.insert(0, level_node)
                results.append(result)
            
        return results