LeetCode 107. 二叉树的层次遍历 II | Python

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode 107. 二叉树的层次遍历 II | Python，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1407字，纯文字阅读大概需要3分钟。

内容图文

107. 二叉树的层次遍历 II

---

题目

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii

---

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：

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

    3
   /   9  20
    /     15   7

返回其自底向上的层次遍历为：

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

解题思路

---

思路：广度优先搜索（BFS）

先看题目，题目要求返回节点值自底向上的层次遍历。（从叶子节点所在层往根节点所在层，逐层从左到右遍历）。

那么我们可以发现，使用广度优先搜索的方法是最直观的，题目要求自底向上，这里我从上到下遍历搜索时先用栈存储，然后再实现逆序（即自底向上）。具体的做法如下：

• 从根节点开始搜索；
• 每次搜索的时候先确定当前层的节点数量，遍历当前层的全部节点，用列表存储当前层的节点值；
• 用栈存储上述存储每层节点值的列表，后续实现逆序。

具体代码实现如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        ans = []

        stack = []

        queue = deque()
        queue.append(root)

        while queue:
            cnt = len(queue)
            
            tmp = []

            for _ in range(cnt):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                tmp.append(node.val)
            
            stack.append(tmp)
        
        while stack:
            ans.append(stack.pop())
        
        return ans

欢迎关注

---

公众号 【书所集录】

内容总结

以上是互联网集市为您收集整理的LeetCode 107. 二叉树的层次遍历 II | Python全部内容，希望文章能够帮你解决LeetCode 107. 二叉树的层次遍历 II | Python所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---