LeetCode-Python-102. 二叉樹的層次周遊

給定一個二叉樹，傳回其按層次周遊的節點值。 （即逐層地，從左到右通路所有節點）。

例如:

給定二叉樹: 

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

,

3
   / \
  9  20
    /  \
   15   7
           

傳回其層次周遊結果：

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

思路：

BFS, 處理每一層的時候記錄下一層的節點，并把目前這一層每個節點的值記錄到結果裡。

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        node = [root]
        result = list(list())
        self.generate(node, result)
        return result
    
    def generate(self, node, result):
        next_layer_node = []
        current_layer_result = []

        for node in node:
            if node.left:
                next_layer_node.append(node.left)
            if node.right:
                next_layer_node.append(node.right)
            current_layer_result.append(node.val)

        result.append(current_layer_result)
        if len(next_layer_node) == 0:
            return

        self.generate(next_layer_node, result)
           

下面的寫于2019.6.24 

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        queue = [root]
        res = []
        while queue:
            next_queue = []
            layer = []
            for node in queue:
                if node:
                    layer.append(node.val)
                    next_queue += [node.left, node.right]
            queue = next_queue[:]
            if layer:
                res.append(layer[:])
        return res