102. Binary Tree Level Order Traversal.md

102. Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/

solution

• 如果需要区分bfs的每一层，需要每一层更新队列；如果不区分每层，采用队列的push、pop

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        queue = collections.deque([root])
        res = []
        while queue:
            levels = []  # 树每层新开一个array，保存结果
            for _ in range(len(queue)):  # 每层结果单独一个array间隔的关键在增加一层for，且for循环次数要保持刚进入循环时的size
                node = queue.popleft()
                levels.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(levels)
        return res

时间复杂度：O(n)
空间复杂度：O(n)

follow-up

429. N-ary Tree Level Order Traversal

"""
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return []

        levels = collections.deque([root])
        res = []
        while levels:
            level_res = []
            for i in range(len(levels)):  # 按层bfs会有一个对层的for循环
                node = levels.popleft()
                level_res.append(node.val)
                for child in node.children:  # 该层的node如果存在下一层则进入队列
                    if child:
                        levels.append(child)
            res.append(level_res)
        return res

时间复杂度：O()
空间复杂度：O()

107. Binary Tree Level Order Traversal II

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        queue = [root]
        res = []
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                level.append(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(level)

        return res[::-1]