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 7return 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)
腾讯云开发者
