小数乘法计算题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)


相关推荐

  • 微信公众号开发教程(一) 验证接入[通俗易懂]

    作者:陈惠,叩丁狼教育高级讲师。原创文章,转载请注明出处。微信公众号开发教程(一)验证接入本篇文章主要介绍了微信公众号开发接入详细流程,希望对刚接触公众号开发的同学有所帮助,有兴趣的同学可多多关注叩丁狼公众号,后续会更新不同的公众号小案例。公众号的分类我们平常在微信应用上会看到有很多的公众号,但是各自并不一样,公众号也分很多种类型,不过最常见的就是服务号和订阅号了。下面我们来看一下他们的区别:1、…

  • java如何输入字符串_JAVA中怎样输入字符串「建议收藏」

    java如何输入字符串_JAVA中怎样输入字符串「建议收藏」https://zhidao.baidu.com/question/344967589.htmljava.lang.String.charAt()方法返回指定索引处的char值。http://www.yiibai.com/javalang/string_charat.html(toLowerCase)toUpperCase的意思是将所有的英文字符转换为大写字母,如:Stringcc=“a…

  • 多项式除法例子_方程除法怎么算

    多项式除法例子_方程除法怎么算问题描述给定一个$n$次多项式$F(x)$和一个$m$次多项式$G(x)$,请求出多项式$Q(x)$,$R(x)$,满足以下条件:$Q(x)$次数为$n-m$,$R(x)$次数

  • es6模板字符串里用html标签,为ES6模板字符串计算标签函数[通俗易懂]

    es6模板字符串里用html标签,为ES6模板字符串计算标签函数[通俗易懂]Python部落(python.freelycode.com)组织翻译,禁止转载,欢迎转发。这篇博客描述了你可以通过函数为ES6模板字符串做些什么从而获取返回值。对于一篇针对模板字符串的介绍来说,标记的模板字符串和函数需要在《探索ES6》中查询模板字符串章节1.通过模板字符串获取返回值在JavaScript中获取一个值最普遍的方法就是在括号中加上参数。在ES6中,你可以通过模板字符串更多地获取返回…

  • Python Tkinter+py2exe[通俗易懂]

    Python Tkinter+py2exe[通俗易懂]最近写小工具,用了pyhon的Tkinter,mark一下,省的到处去找。。。第一波:标签Label,文本框Entry,按钮Button,Text文本域#coding:utf-8fromTkinterimport*root=Tk()#创建主窗口label=Label(master=root,text=”这是一个标签”)label.grid(row=0,c

  • hive sql分页[通俗易懂]

    hive sql分页[通俗易懂]查出线上线下会员支付超过100的 select*from(  selecta.id,b.mobile,a.totalmoneyfrom (SELECTsum(totalmoney)totalmoney,idFROM  (SELECTt.totalmoney,d.idFROM(  SELECTsum(totalmoney)totalmoney,vipcardn…

    2022年10月21日

发表回复

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

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