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

兴趣爱好交流 每日一题
1

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

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

例如:

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


    3

   / \

  9  20

    /  \

   15   7

返回其层次遍历结果：


[

  [3],

  [9,20],

  [15,7]

]

提示：


节点总数 <= 1000

来源：力扣（LeetCode）

链接：力扣

一解

使用广度遍历：

  • 将同一层级树节点存储在 nodes 中

  • 遍历 nodes ,取出“当前结点值”和“下一层树结点”


# 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[List[int]]:

        if not root:

            return []

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

        queue.append(root)

        while queue:

            nodes = []

            while queue:

                nodes.append(queue.popleft())

            result.append([i.val for i in nodes])

            for node in nodes:

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

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

        return result

二解

思路与一解相同，由于for _ in range(len(queue))的循环次数固定（len(queue)），不会随queue的大小进行变化（while queue），因此可将queue.append操作放入循环内：


# 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[List[int]]:

        if not root: return []

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

        queue.append(root)

        while queue:

            nodes = []

            for _ in range(len(queue)):

                node = queue.popleft()

                nodes.append(node.val)

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

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

            result.append(nodes) 

        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:
        sub_results = []
        new_deque = collections.deque()
        while deque:
            node = deque.popleft()
            sub_results.append(node.val)
            if node.left: new_deque.append(node.left)
            if node.right: new_deque.append(node.right)
        deque = new_deque
        result.append(sub_results)
    return result


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