剑指Offer32-I-从上到下打印二叉树

兴趣爱好交流 每日一题
1

剑指Offer32-I-从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:

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


    3

   / \

  9  20

    /  \

   15   7

返回：


[3,9,20,15,7]

提示：


节点总数 <= 1000

来源：力扣（LeetCode）

链接：力扣

一解

典型的广度优先遍历搜索（BFS），可使用队列的先入先出实现。以下面的二叉树为例，其结果 [3, 9, 20, 15, 17]：


    3

   / \

  9  20

    /  \

   15   17




# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def levelOrder(self, root: TreeNode) -> List[int]:

        if not root: return []

        result, queue = [], collections.deque()

        queue.append(root)

        while queue:

            node = queue.popleft()

            result.append(node.val)

            if node.left: queue.append(node.left)

            if node.right: queue.append(node.right)

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


class Tree:
    def __init__(self, node_values: list):
        nodes = [TreeNode(i) if i else None for i in node_values]
        self.root = nodes[0]
        n = 0
        while 2 * n + 1 < len(nodes):
            nodes[n].left, nodes[n].right = nodes[2 * n + 1], nodes[2 * n + 2]
            n += 1


import collections


def level_order(root: TreeNode):
    if not root:
        return []
    result, deque = [], collections.deque()
    deque.append(root)
    while deque:
        node = deque.popleft()
        result.append(node.val)
        if node.left: deque.append(node.left)
        if node.right: deque.append(node.right)

    return result


assert (level_order(Tree([3, 9, 20, None, None, 15, 7], ).root)) == [3, 9, 20, 15, 7]