[LeetCode] 103. Binary Tree Zigzag Level Order Traversal

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

二叉树的锯齿形层序遍历。

题意是给一个二叉树，对其进行层序遍历，但是在遍历每一层的时候要一次从左开始一次从右开始。

思路和102题的做法 - 层序遍历没两样，唯一需要多一个变量记录到底是从左遍历还是从右遍历。

时间O(n)

空间O(n) - 记录output

JavaScript实现

 1 /**
 2  * @param {TreeNode} root
 3  * @return {number[][]}
 4  */
 5 var zigzagLevelOrder = function (root) {
 6     var res = [];
 7     // corner case
 8     if (root === null) {
 9         return res;
10     }
11 
12     // normal case
13     var queue = [];
14     queue.push(root);
15     var x = true;
16     while (queue.length > 0) {
17         var size = queue.length;
18         var list = [];
19         for (var i = 0; i < size; i++) {
20             var cur = queue.shift();
21             if (x) {
22                 list.push(cur.val);
23             } else {
24                 list.unshift(cur.val);
25             }
26             if (cur.left !== null) {
27                 queue.push(cur.left);
28             }
29             if (cur.right !== null) {
30                 queue.push(cur.right);
31             }
32         }
33         res.push(list);
34         x = !x;
35     }
36     return res;
37 };

Java实现

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 class Solution {
11     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
12         List<List<Integer>> res = new ArrayList<>();
13         // corner case
14         if (root == null) {
15             return res;
16         }
17 
18         // normal case
19         Queue<TreeNode> queue = new LinkedList<>();
20         queue.offer(root);
21         boolean x = true;
22         while (!queue.isEmpty()) {
23             int size = queue.size();
24             List<Integer> list = new ArrayList<>();
25             for (int i = 0; i < size; i++) {
26                 TreeNode cur = queue.poll();
27                 if (x) {
28                     list.add(cur.val);
29                 } else {
30                     list.add(0, cur.val);
31                 }
32                 if (cur.left != null) {
33                     queue.offer(cur.left);
34                 }
35                 if (cur.right != null) {
36                     queue.offer(cur.right);
37                 }
38             }
39             res.add(list);
40             x = !x;
41         }
42         return res;
43     }
44 }

LeetCode 题目总结