刷题

简介: 给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

一、题目描述:

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

示例 1:

img

输入:root = [3,9,20,null,null,15,7]
输出:[[15,7],[9,20],[3]]
示例 2:

输入:root = [1]
输出:[[1]]
示例 3:

输入:root = []
输出:[]

提示:

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/binary-tree-level-order-traversal-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、思路分析:

结果需要自底向上,直接自底向上显然不好实现,所以可以采用自顶向下层次遍历,然后再反转即可得到。
如果用一个队列进行层次遍历,会有一个麻烦,就是不知道每一层什么时候结束,就没办法将每一层的数据分别用不同集合来存储。
所以可以采用两个队列来实现,一个队列遍历当前层,一个队列存储下一层,交替使用,达到目的。

三、AC 代码:

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        //解题思路:DFS遍历,注意结果采用头插法
        List<List<Integer>> result = new ArrayList();
        dfs(result, root, 0);
        return result;
    }

    private void dfs(List<List<Integer>> result, TreeNode root, int level){
        if(root == null){
            return;
        }
        //初始化新的层在第一行
        if(level == result.size()){
            result.add(0, new ArrayList());
        }
        //写入结果集;第level层要插入从后往前数的第level层
        result.get(result.size() - level - 1).add(root.val);
        
        //左子树
        dfs(result, root.left, level + 1);
        //右子树
        dfs(result, root.right, level + 1);
    }
}
AI 代码解读
目录
打赏
0
0
0
0
4
分享
相关文章
ubunut16.04 make install 提示 makeinfo is missing on your system;
ubunut16.04 make install 提示 makeinfo is missing on your system;
173 2
IDEA中Git面板操作介绍 变基、合并、提取、拉取、签出
在IDEA的Git面板中,仓库会分为本地仓库和远程仓库,代码仓库里面放的是各个分支。
2408 2
队列的深度解析:链式队列的实现
队列的深度解析:链式队列的实现
|
12月前
【vue2】vue2 实现手风琴效果,复制粘贴直接使用
【vue2】vue2 实现手风琴效果,复制粘贴直接使用
263 1
vue-baidu-map 百度地图检索、获取坐标
vue-baidu-map 百度地图检索、获取坐标
222 1
【红队APT】钓鱼篇&Office-CVE&RLO隐藏&压缩包释放&免杀打包捆绑
【红队APT】钓鱼篇&Office-CVE&RLO隐藏&压缩包释放&免杀打包捆绑
188 1
|
12月前
|
【Axure】axure rp 导入元件库和使用,主流元件库下载使用
【Axure】axure rp 导入元件库和使用,主流元件库下载使用
2144 1
阿里云EMR数据湖文件系统问题之JindoFSOSS的单一prefix热点的问题如何解决
阿里云EMR数据湖文件系统问题之JindoFSOSS的单一prefix热点的问题如何解决

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问