小数乘法计算题100道_leetcode题库c语言

小数乘法计算题100道_leetcode题库c语言LeetCode算法题-Binary Tree Level Order Traversal II(Java实现)

大家好,又见面了,我是你们的朋友全栈君。

这是悦乐书的第165次更新,第167篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第24题(顺位题号是107)。给定二叉树,返回其节点值的自下而上级别顺序遍历(即从左到右,逐层逐层)。例如:

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

    3
   / \
  9  20
     / \
    15  7

返回其自下而上的级别顺序遍历:[[15,7],[9,20],[3]]。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

特殊情况:当传入的二叉树为空时,返回我们新定义的空List即可。

正常情况:从示例最后要求输出的结果来看,根节点是数组的最后一位元素,如果是自顶向下遍历节点,我们可以使用队列,借助其先进先出的特点,一层一层遍历节点,将每一层遍历的节点值存入List中,再将List放入List2中,最后再倒序遍历List2存入List3中,List3就是最后的结果。

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> list2 = new ArrayList<>();
    if (root == null) {
        return list2;
    }
    List<Integer> list = new ArrayList<Integer>();
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        list = new ArrayList<Integer>();
        Queue<TreeNode> tem = new LinkedList<>();
        while (!q.isEmpty()) {
            TreeNode t = q.poll();
            list.add(t.val);
            if (t.left != null) {
                tem.add(t.left);
            }
            if (t.right != null) {
                tem.add(t.right);
            }
        }
        list2.add(list);
        q = tem;
    }
    List<List<Integer>> list3 = new ArrayList<>();
    for(int i=list2.size()-1; i >= 0; i--){
        list3.add(list2.get(i));
    }
    return list3;
}

遍历节点的处理方法和昨天那道求最长路径的写法类似,借助队列先进先出的特点,从左往右依次循环。

03 第二种解法

我们可以将第一种解法再优化下,不再创建新的队列来存新的一层的节点。和昨天那道题的写法类似,借助队列的size来作为判断条件。

public List<List<Integer>> levelOrderBottom2(TreeNode root) {
    List<List<Integer>> list2 = new ArrayList<>();
    if (root == null) {
        return list2;
    }
    List<Integer> list = new ArrayList<Integer>();
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        list = new ArrayList<Integer>();
        int n = q.size();
        while (n-- > 0) {
            TreeNode t = q.poll();
            list.add(t.val);
            if (t.left != null) {
                q.offer(t.left);
            }
            if (t.right != null) {
                q.offer(t.right);
            }
        }
        list2.add(list);
    }
    List<List<Integer>> list3 = new ArrayList<>();
    for(int i=list2.size()-1; i >= 0; i--){
        list3.add(list2.get(i));
    }
    return list3;
}

04 第三种解法

上面两种解法都是使用新的List来存储List2倒序遍历的值作为最后结果返回,既然是先进后出的特点,我们可以使用栈来存储每遍历一层节点存入的List,再使用栈的pop方法出栈存入新的List。

public List<List<Integer>> levelOrderBottom3(TreeNode root) {
    List<List<Integer>> list2 = new ArrayList<>();
    if (root == null) {
        return list2;
    }
    List<Integer> list = new ArrayList<Integer>();
    Stack<List<Integer>> stack = new Stack<List<Integer>>();
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        list = new ArrayList<Integer>();
        int n = q.size();
        while (n-- > 0) {
            TreeNode t = q.poll();
            list.add(t.val);
            if (t.left != null) {
                q.offer(t.left);
            }
            if (t.right != null) {
                q.offer(t.right);
            }
        }
        stack.add(list);
    }
    while (!stack.isEmpty()) {
        list2.add(stack.pop());
    }
    return list2;
}

05 第四种解法

上面的三种都是使用遍历的方式,那我们可不可以使用递归的方法遍历每一层的节点值?显然是可以的,我们可以使用层数作为标记,来判断现阶段处于那一层,从而来决定是新建一个List还是取已存在的List往里面存入新的节点值。

public List<List<Integer>> levelOrderBottom4(TreeNode root) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    List<List<Integer>> node = new ArrayList<List<Integer>>();
    viewTree(root, res, 0);
    for (int i=res.size()-1; i>=0; i--) {
        node.add(res.get(i));
    }
    return node;
}

public void viewTree(TreeNode root, List<List<Integer>> res, int deep) {
    if(root == null)
        return;
    if (res.size() <= deep) {
        List<Integer> node = new ArrayList<Integer>();
        node.add(root.val);
        res.add(node);   
    } else {
        List<Integer> node = (List<Integer>)res.get(deep);
        node.add(root.val);
    }
    viewTree(root.left, res, deep+1);
    viewTree(root.right, res, deep+1);
}

从根节点开始,先递归获取根节点左子节点及其子节点的节点值,然后再递归获取根节点右子节点及其子节点的节点值。

06 验证与测试

对于上面四种解法,我们选取了一个四层的二叉树来作为测试数据,测试代码如下:

public static void main(String[] args) {
    Easy_107_BinaryTreeLevelOrderTraversalII instance = new Easy_107_BinaryTreeLevelOrderTraversalII();
    TreeNode t = new TreeNode(1);
    TreeNode t2 = new TreeNode(2);
    TreeNode t3 = new TreeNode(3);
    TreeNode t4 = new TreeNode(4);
    TreeNode t5 = new TreeNode(5);
    TreeNode t6 = new TreeNode(6);
    TreeNode t7 = new TreeNode(7);
    TreeNode t8 = new TreeNode(8);
    t.left = t2;
    t.right = t3;
    t2.left = t4;
    t2.right = t5;
    t3.left = t6;
    t3.right = t7;
    t7.left = t8;
    long start = System.nanoTime();
    List<List<Integer>> result = instance.levelOrderBottom(t);
    long end = System.nanoTime();
    System.out.println("levelOrderBottom---输出:"+result.toString()+" , 用时:"+(end-start)/1000+"微秒");
    long start2 = System.nanoTime();
    List<List<Integer>> result2 = instance.levelOrderBottom2(t);
    long end2 = System.nanoTime();
    System.out.println("levelOrderBottom2---输出:"+result2.toString()+" , 用时:"+(end2-start2)/1000+"微秒");
    long start3 = System.nanoTime();
    List<List<Integer>> result3 = instance.levelOrderBottom3(t);
    long end3 = System.nanoTime();
    System.out.println("levelOrderBottom3---输出:"+result3.toString()+" , 用时:"+(end3-start3)/1000+"微秒");
    long start4 = System.nanoTime();
    List<List<Integer>> result4 = instance.levelOrderBottom4(t);
    long end4 = System.nanoTime();
    System.out.println("levelOrderBottom4---输出:"+result4.toString()+" , 用时:"+(end4-start4)/1000+"微秒");
}

测试结果如下:

levelOrderBottom---输出:[[8], [4, 5, 6, 7], [2, 3], [1]] , 用时:446微秒
levelOrderBottom2---输出:[[8], [4, 5, 6, 7], [2, 3], [1]] , 用时:24微秒
levelOrderBottom3---输出:[[8], [4, 5, 6, 7], [2, 3], [1]] , 用时:55微秒
levelOrderBottom4---输出:[[8], [4, 5, 6, 7], [2, 3], [1]] , 用时:23微秒

因为只是采用单一数据测试,样本数量过少,无法得出太过准确的结论,但还是可以明显看出解法二和解法四其他条件一样的情况下用时是最少的。

07 小结

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

转载于:https://www.cnblogs.com/xiaochuan94/p/9927092.html

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

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107205.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • map.containsKey方法的运用「建议收藏」

    map.containsKey方法的运用「建议收藏」map之containsKey方法例如:List<HashMap<String,Object>>pt=mapperDao.query(param1,param2);for(HashMap<String,Object>map:pt){if(!map.containsKey(“age”)||null==map.get(“age”))c…

  • 录制gif工具_GIF录制

    录制gif工具_GIF录制LicecapforMac下载地址下载完成后打开软件,界面如下图。整个软件界面为透明层,左下角可以设置图片FPS,右下角又两个按钮,分别为录制按钮和停止按钮。鼠标移动至软件边框处可以改变软件界面大小,这个大小就是你将要录制的界面大小。点击右下角record录制按钮,选择保存位置后,开始录制。点击录制按钮后,软件透明区域中的模拟器变为了可操作区域,进行一些操作后,点击stop停止按钮。在保存位置处生成一张gif图片。注意:发现无法录屏,可以通过设置打开录屏权限…

  • 让我郁闷的第一次做站[通俗易懂]

    让我郁闷的第一次做站[通俗易懂]我是今年7月份毕业的,我在学校学的软件专业,但是在学校的时候很贪玩,没学到多少东西,毕业后找本专业的工作处处碰壁找不到,后来去了个seo公司,他们是做英文的,这也是我第一次接触这个行业,原来不知道seo的存在。这个公司很小的,其实主要的业务都是给别人代发外链,我也就成了外链专员。因为刚接触连seo是什么都不知道,我就在网上到处找相关的论坛视频教程看,发现很多教程都是要收费的,不收费的讲的太潦草,有

  • zip文件加密的几种破解方法

    zip文件加密的几种破解方法一、使用ZipCenOp.jar(需要java环境),在cmd中使用java-jarZipCenOp.jarrxxx.zip成功后压缩包可以直接打开ZipCenOp.jar链接:https://pan.baidu.com/s/1e0Ni2OjxmYEdOY7gGbv6gg提取码:29qi二、使用winRAR进入工具,压缩修复文件,修复完后压缩包就可以打开了上述两种…

  • CSS3橙色的星球绕轨道公转动画

    效果:http://hovertree.com/texiao/css3/24/效果图:代码如下:转自:http://hovertree.com/h/bjaf/css3xingxi.htm特效汇总:

    2021年12月24日
  • 数据结构课程设计哈希表的设计与实现课程设计(数据结构哈希表查找姓名设计)

    我负责小组里处理冲突。用RN【30】做随即数列。在冲突的时候使用作为随即增量。为防止重复,在赋值时做适当处理。这是处理前的代码:#include#include#include#include#include#includeusingnamespacestd;#defineMAX_NUM26typedefstructPreson//定义数

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号