算法题--分层收集二叉树中的元素

image.png

0. 链接

题目链接

1. 题目

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

2. 思路1: 递归实现

• 定义遍历方法，带有参数node, level, results
• 将node收集到results[level-1]中去之后, 继续递归收集下一层的节点node.left, node.right 且level+1

3. 代码

# coding:utf8
from typing import List


# 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]]:
        def traversal(node, level, results):
            if node is None:
                return
            if len(results) < level:
                results.append(list())
            results[level - 1].append(node.val)
            traversal(node.left, level + 1, results)
            traversal(node.right, level + 1, results)

        results = list()
        traversal(root, 1, results)
        return results


solution = Solution()

root1 = node = TreeNode(3)
node.left = TreeNode(9)
node.right = TreeNode(20)
node.right.left = TreeNode(15)
node.right.right = TreeNode(7)

print(solution.levelOrder(root1))

输出结果

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

4. 结果

image.png