算法题--从底向上分层收集二叉树中的节点值

image.png

0. 链接

题目链接

1. 题目

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

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

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

2. 思路1: 递归实现

• 从根节点逐渐往底层遍历收集节点
• 记录初始层level

level=1

• 新增一层时新建列表
  当results长度小于level时, 需要在results最前面插入一个列表来收集当前最底层节点

results.insert(0, list())

• 将节点收集到它所在层的列表中

results[len(results) - level].append(node.val)

3. 代码

# coding:utf8
from typing import List


# 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:

        def check(results, node, level=1):
            if len(results) < level:
                results.insert(0, list())
            results[len(results) - level].append(node.val)
            if node.left is not None:
                check(results, node.left, level + 1)
            if node.right is not None:
                check(results, node.right, level + 1)

        results = list()
        if root is not None:
            check(results, root)
        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.levelOrderBottom(root1))

输出结果

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

4. 结果

image.png

5. 利用队列(BFS)

• 使用一个队列记录下一层要处理的节点
• 每次都处理当前一层, 然后将下一层要处理的节点追加到记录末尾

6. 代码

class Solution1:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        results = list()
        if root is None:
            return results

        queue = list()
        queue.append(root)

        while len(queue) > 0:
            level_num = len(queue)
            sub_list = list()
            for i in range(level_num):
                if queue[0].left is not None:
                    queue.append(queue[0].left)
                if queue[0].right is not None:
                    queue.append(queue[0].right)
                sub_list.append(queue.pop(0).val)
            results.insert(0, sub_list)

        return results


solution = Solution1()

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

print(solution.levelOrderBottom(root1))

输出结果

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

7. 结果

image.png