1 題目描述

給定一個二元樹，返回其節點值的層序遍歷。換句話說，從左到右，逐層遍歷所有節點。

2 解法

這題很明顯，我們可以使用BFS的方式來解，因為BFS是一種逐層遍歷的方式。

我們會需要

next_level 來存放下一層的節點，然後透過呼叫自己，放入next_level的節點。
nodes 是當層的所有節點。
values 是用來存放當層的節點值。
result 就是結果。

Recursive

class Solution: 
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        def bfs_helper(nodes):
            if not nodes:
                return
            next_level, values = [], []
            for node in nodes:
                values.append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            result.append(values)
            bfs_helper(next_level)
        
        result = []
        if root:
            helper(root, 0)
        return result

Iterator
也可以把它寫成迭代的方式。

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        result = []
        nodes = [root]
        
        while nodes:    # 當nodes不為空
            next_level = []
            values = []
            for node in nodes:
                values.append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            result.append(values)
            nodes = next_level  # 每次遍歷完當層的節點後，把next_level放入nodes，這樣下次迭代就會遍歷下一層的節點
        return result