leetCode-二叉树的层序遍历 II

题目地址:二叉树的层序遍历 II

解题思路

本文解题思路来自左程云老师算法课新手班第七节

题目要求返回的是链表套链表 ,而且是倒序。不妨先考虑正序输出

正序输出也就是另一道leetCode的题 二叉树的层序遍历

假设有这么一颗树

正序返回就是[[1],[2,3],[4,5,6,7],[8,9,10]]。

我们可以考虑使用队列来解决

定义一个队列queue,首先将root传入队列,

Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);

当前queue内有一个节点,进行一次如下操作,先将该节点弹出到一个链表内,如果左支不为空,就将左支塞入队列,右支不为空也塞入队列,现在queue内是[2,3]。正好为第二层。

现在queue内有两个节点,执行两次上述操作,那么现在也会出现一个链表为[2,3],那么进行两次操作,

弹出2,2的左支塞入队列,现在queue为[3,4],2 的右支塞入队列,为[3,4,5]。第一次操作结束。弹出3,依然左支,右支塞入,现在queue为 [4,5,6,7]。

 while (!queue.isEmpty()) {
    int size = queue.size();
    List<Integer> curAns = new LinkedList<>();
    for (int i = 0; i < size; i++) {
        TreeNode curNode = queue.poll();
        curAns.add(curNode.val);
        if (curNode.left != null) {
             queue.add(curNode.left);
        }
        if (curNode.right != null) {
            queue.add(curNode.right);
        }
    }
}

所以现在只有将这些链表逆序输出的过程了

我们可以在循环外面定义一个List<List<Integer>>。在内部循环结束时,使用add方法。去在0位置插入每一个生成的链表那么最后生成的最深层就是会返回的头。

ans.add(0, curAns);

返回对象的选择 ArrayList or LinkedList

那么就需要看看是使用ArrayList还是使用LinkedList

可以通过一个小测试,去看一看那种更优

使用这个System.currentTimeMillis();,在循环前后就可以得出该循环的用时。

    public static void main(String[] args) {
        int TestTime = 10000;
        long start;
        long end;
        ArrayList<Integer> list1 = new ArrayList<>();
        start = System.currentTimeMillis();
        for (int i = 0;i<TestTime;i++){
            list1.add(0,i);
        }
        end  = System.currentTimeMillis();
        System.out.println(end - start);
        LinkedList<Integer> list2 = new LinkedList<>();
        start = System.currentTimeMillis();
        for (int i = 0;i<TestTime;i++){
            list2.add(0,i);
        }
        end  = System.currentTimeMillis();
        System.out.println(end - start);
    }

当TestTime为1 0000时,对比结果为4:1

当TestTime为10 0000时,对比结果为344:2

当TestTime为100 0000时,对比结果为14 3158:151

对比已经很明显。LinkedList的效率明显优于ArrayList。所以我们选用LinkedList做为我们的返回对象

List<List<Integer>> ans = new LinkedList<>();

完整代码

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> curAns = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.poll();
                curAns.add(curNode.val);
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            ans.add(0, curAns);
        }
        return ans;
    }
版权声明:除特殊说明,博客文章均为栋dong原创,依据CC BY-SA 4.0许可证进行授权,转载请附上出处链接及本声明。
如有需要,请在留言板留言,或者添加我的QQ或者微信
我只是一个学生,如有错误或者侵权,请联系我,谢!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
春节
快乐