☆打卡算法☆LeetCode 107、二叉树的层序遍历 II 算法解析
☆打卡算法☆LeetCode 107、二叉树的层序遍历 II 算法解析
恬静的小魔龙
发布于 2022-08-07 10:25:45
发布于 2022-08-07 10:25:45
一、题目
1、算法题目
“给定二叉树根节点，返回节点值自底向上的层序遍历。”
题目链接：
来源：力扣（LeetCode）
链接：107. 二叉树的层序遍历 II - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。
image.png
示例 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;
}
}
image.png
3、时间复杂度
时间复杂度 ： O(n)
其中n是树中的节点个数。每个节点访问一次，结果列表使用链表的结构，在结构列表头部添加一层节点值的列表的时间复杂度为O(1)，因此总时间复杂度为O(n)。
空间复杂度： O(n)
其中n是树中的节点个数。
三、总结
为了降低在结果列表头部添加一层节点值的列表的时间复杂度，结果列表可以使用链表的结构。
在代码中，需要返回List类型的数据，可以使用链表实现。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-04-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录