一、题目
1、算法题目
“给定二叉树根节点，返回节点值自底向上的层序遍历。”
题目链接：
来源：力扣（LeetCode）
链接：107. 二叉树的层序遍历 II - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。
网络异常，图片无法展示
|
示例 1： 输入： root = [3,9,20,null,null,15,7] 输出： [[15,7],[9,20],[3]] 复制代码
示例 2： 输入： root = [1] 输出： [[1]] 复制代码
二、解题
1、思路分析
这道题和102题二叉树的层序遍历类似，不同的地方在于102题要求从上到下输出每一层的节点值。
这一题是从下到上输出每一层的节点值。
虽然说输出顺序不同，但是思路是相同的，都可以使用广度优先搜索记性层次遍历。
从根节点开始搜索，每次遍历同一层的全部节点，使用列表存储改层的节点值。
在遍历完一层节点之后，将存储该层节点值的列表添加到结果列表的头部。
2、代码实现
代码参考：
class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> levelOrder = new LinkedList<List<Integer>>(); if (root == null) { return levelOrder; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { List<Integer> level = new ArrayList<Integer>(); 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; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n)
其中n是树中的节点个数。每个节点访问一次，结果列表使用链表的结构，在结构列表头部添加一层节点值的列表的时间复杂度为O(1)，因此总时间复杂度为O(n)。
空间复杂度： O(n)
其中n是树中的节点个数。
三、总结
为了降低在结果列表头部添加一层节点值的列表的时间复杂度，结果列表可以使用链表的结构。
在代码中，需要返回List类型的数据，可以使用链表实现。
