LeetCode: 102. Binary Tree Level Order Traversal

题目

原题地址：https://leetcode.com/problems/binary-tree-level-order-traversal/

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:

Given binary tree [3,9,20,null,null,15,7],

  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

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

解法

广度优先，从上到下一层一层遍历，保存每一层的 value。

这个方法的 Python 代码类似下面这样:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        all_values = []
        next_level_nodes = [root]

        while next_level_nodes:
            current_nodes = next_level_nodes
            values = []
            next_level_nodes = []
            for node in current_nodes:
                values.append(node.val)
                if node.left is not None:
                    next_level_nodes.append(node.left)
                if node.right is not None:
                    next_level_nodes.append(node.right)
            if values:
                all_values.append(values)

        return all_values

Comments