Baozi Training Leetcode solution 103:BinaryTree Zigzag Traversal

包子面试培训

发布于 2019-10-24 20:44:03

3410

发布于 2019-10-24 20:44:03

文章被收录于专栏：包子铺里聊IT包子铺里聊IT

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],

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