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

兴趣爱好交流 每日一题
1

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

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:

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


    3

   / \

  9  20

    /  \

   15   7

返回其层次遍历结果：


[

  [3],

  [20,9],

  [15,7]

]

提示：


节点总数 <= 1000

来源：力扣（LeetCode）

链接：力扣

一解

使用广度遍历：

  • 通过反转输出内容（tmp[::-1]），实现“之字形”打印

  • 通过判断 res 长度是奇，偶，判定是否进行反转


# 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 []

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

        queue.append(root)

        while queue:

            tmp = []

            for _ in range(len(queue)):

                node = queue.popleft()

                tmp.append(node.val)

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

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

            res.append(tmp[::-1] if len(res) % 2 else tmp)

        return res
2 
from typing import List


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) -> List[List[int]]:
    result = []
    deque = collections.deque()
    deque.append(root)
    while deque:
        tmp = []
        for _ in range(len(deque)):  # deque的长度动态变化，但是只要记住一开始的长度，就可以拿到那一层的所有node
            node: TreeNode = deque.popleft()
            tmp.append(node.val)
            if node.left: deque.append(node.left)
            if node.right: deque.append(node.right)
        result.append(tmp[::-1] if len(result) % 2 == 1 else tmp)
    return result


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