大家好!我是你们的好朋友，大数据老虾。相遇是缘，既然来了就拎着小板凳坐下来一起唠会儿，如果在文中有所收获，请别忘了一键三连，你的鼓励，是我创作的动力，废话不多说，直接开干 吧。
先别急着走，文末干货，记得拎着小板凳离开的时候也给它顺走藍
树-二叉树的层序遍历 ||二叉树的层序遍历 ||
题目方法1：广度优先搜索
树的层次遍历可以使用广度优先搜索实现 Java实现代码复杂度分析Python实现代码文末彩蛋朗
二叉树的层序遍历 || 题目给出二叉树的根节点root，返回其节点值自底向上的层序遍历。(即按从叶子节点所在的层到根节点所在的层，逐层从左向右遍历)
示例1：
input：root = [3, 9, 20, null, null, 15, 7] output：[[15, 7], [9, 20, [3]]]
示例2：
input：root = [1] output：[[1]]
示例3：
input：root = [] output：[]方法1：广度优先搜索
解析：
1、二叉搜索的层序遍历 | 中，要求从上到下出书每一层的节点值
2、二叉树的层序遍历 || 中，要求从下到上输出每一层的节点值
PS：仅仅输出顺序不同
树的层次遍历可以使用广度优先搜索实现1、从根节点开始搜索，每次遍历同一层的全部节点，使用一个列表存储该层的节点值。
2、如果要求从上到下输出每一层的节点值，做法是很直观的，在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的尾部。
3、为了降低在结果列表的头部添加一层节点值的列表的时间复杂度，结果列表可以使用链表的结构，在链表头部添加一层节点值的列表的时间复杂度是 O(1)。
4、在 Java 中，由于需要返回的 List 是一个接口，这里可以使用链表实现；而 C++ 或 Python 中，需要返回一个 vector 或 list，它不方便在头部插入元素（会增加时间开销），所以可以先用尾部插入的方法得到从上到下的层次遍历列表，然后再进行反转。
Java实现代码class Solution {
public List> levelOrderBottom(TreeNode root) {
List> levelOrder = new linkedList>();
if (root == null) {
return levelOrder;
}
Queue queue = new linkedList();
queue.offer(root);
while (!queue.isEmpty()) {
List level = new ArrayList();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
TreeNode left = node.left, right = node.right;
if (left != null) {
queue.offer(left);
}
if (right != null) {
queue.offer(right);
}
}
levelOrder.add(0, level);
}
return levelOrder;
}
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
复杂度分析
时间复杂度：O(n)，其中 n 是二叉树中的节点个数。每个节点访问一次，结果列表使用链表的结构时，在结果列表头部添加一层节点值的列表的时间复杂度是 O(1)，因此总时间复杂度是 O(n)。
空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n。
Python实现代码class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
levelOrder = list()
if not root:
return levelOrder
q = collections.deque([root])
while q:
level = list()
size = len(q)
for _ in range(size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
levelOrder.append(level)
return levelOrder[::-1]
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
文末彩蛋朗
找资料很累吧，别急客官，俺统统安排上。程序员不可缺少的书籍，程序员经典名言："收藏了就等于学会啦"
图灵程序丛书300+
Linux实战100讲
Linux书籍
计算机基础硬核总结
计算机基础相关书籍
操作系统硬核总结
Java自学宝典
Java学习资料
Java硬核资料
Java面试必备
Java面试深度剖析
阿里巴巴Java开发手册
MySQL入门资料
MySQL进阶资料
深入浅出的SQL
Go语言书籍
我的个人仓库：私人仓库
