专栏首页包子铺里聊ITBaozi Training Leetcode solution 103:BinaryTree Zigzag Traversal

Baozi Training Leetcode solution 103:BinaryTree Zigzag Traversal

Lime 小绿电动车2019年亏损$300M, 继Uber, Lyft, WeWork 之后,能不能赚钱还是王道呀。寒冬将至,地主家也没有余粮了。。。

Leetcode solution 103: Binary Tree Zigzag Level Order Traversal

Blogger:https://blog.baozitraining.org/2019/10/leetcode-solution-103-binary-tree.html

Youtube: https://youtu.be/ItSAlpdSJtw

博客园: https://www.cnblogs.com/baozitraining/p/11606750.html

B站: https://www.bilibili.com/video/av69354163/

Problem Statement

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

Problem link

Video Tutorial

You can find the detailed video tutorial here

  • Youtube
  • B站

Thought Process

It’s purely an implementation problem to be honest. Very similar to to binary tree level order traversal, we just need to use some data structure to hold the values while we control the traversal order. I choose to use a deque (i.e., doubled linked list) to keep the order. You can also use a queue like many other online solutions but note when calling add(0, value) to an array list is not very efficient since to have array copy every time.

Solutions

 1 // use deque
 2 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
 3     List<List<Integer>> res = new ArrayList<>();
 4     if (root == null) {
 5         return res;
 6     }
 7 
 8     Deque<TreeNode> deque = new LinkedList<>();
 9 
10     deque.add(root);
11     boolean isFromLeftToRight = true;
12 
13     while (!deque.isEmpty()) {
14         int size = deque.size();
15         List<Integer> temp = new ArrayList<>();
16 
17         for (int i = 0; i < size; i++) {
18             if (isFromLeftToRight) {
19                 TreeNode node = deque.pollFirst();
20                 temp.add(node.val);
21 
22                 if (node.left != null) {
23                     deque.addLast(node.left);
24                 }
25                 if (node.right != null) {
26                     deque.addLast(node.right);
27                 }
28             } else {
29                 TreeNode node = deque.pollLast();
30                 temp.add(node.val);
31                 if (node.right != null) {
32                     deque.addFirst(node.right);
33                 }
34                 if (node.left != null) {
35                     deque.addFirst(node.left);
36                 }
37             }
38 
39         }
40         res.add(temp);
41         isFromLeftToRight = !isFromLeftToRight;
42 
43     }
44 
45     return res;
46 }

Time Complexity: O(N) since we visit each node once

Space Complexity: O(N) since used a deque

References

  • Leetcode disucssion solution using add(0,value)

本文分享自微信公众号 - 包子铺里聊IT(baozitraining)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最常见的Android内存优化方式及防止泄漏造成OOM总结篇

    内存优化目的就是让我们在开发中怎么有效的避免我们的应用出现内存泄漏的问题。内存泄漏大家都不陌生了,简单粗俗的讲,就是该被释放的对象没有释放,一直被某个或某些实例...

    Android技术干货分享
  • 腾讯云 | Serverless —— 前端的 3.0 时代

    初次接触前端是读书期间的第一份实习工作,在SAP上海研究院TIP BI部门开发基于SVG的Charts库,99%的代码逻辑是将数据用SVG转化为可视化的UI。值...

    五月君
  • SOFAJRaft—初次使用

    SOFAJRaft 是基于 Raft 算法的生产级高性能 Java 实现,支持 MULTI-RAFT-GROUP。应用场景有 Leader 选举、分布式锁服务、...

    luozhiyun
  • cocos creator | 用摄像机实现残影幻影拖尾效果

    利用摄像机拍摄角色,然后投影到多个显示画布,给画布节点设置不同的透明度,最后让画布节点跟随角色移动。

    张晓衡
  • [Next] 初见next.js

      Next.js 可与 Windows,Mac 和 Linux 一起使用.您只需要在系统上安装 Node.js 即可开始构建 Next.js 应用程序.如果有...

    用户6050340
  • python 手动迭代iter/next

    class Node: def init(self, value): self._value = value self._children = []

    用户5760343
  • 如何修改集群的公网信息(包括 VIP) (文档 ID 1674442.1)

    Oracle Database - Enterprise Edition - 版本 10.1.0.2 到 12.2.0.1 [发行版 10.1 到 12.2] ...

    小麦苗DBA宝典
  • 大前端时代,浅谈JavaScript开发重型跨平台应用以及架构

    https://juejin.im/post/5d8f3062e51d45782632e363

    ConardLi
  • 学会这几个技巧,让Redis大key问题远离你 原

    个推作为国内第三方推送市场的早期进入者,专注于为开发者提供高效稳定的推送服务,经过9年的积累和发展,服务了包括新浪、滴滴在内的数十万APP。由于我们推送业务对并...

    个推君
  • gitbook 入门教程之小白都能看懂的 Gitbook 插件开发全流程

    只要是 Gitbook 默认没有提供的功能,基于插件机制都可以自行扩展,是插件让 Gitbook 变得更加强大.

    雪之梦技术驿站

扫码关注云+社区

领取腾讯云代金券