Baozi Leetcode solution 103: Binary Tree Zigzag Level Order

发布时间：2020-12-14 04:40:30 所属栏目：大数据来源：网络整理

导读：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,15,7]

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!