LeetCode 103 - Binary Tree Zigzag Level Order Traversal - 题解/Solution

*https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
* 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,#,#,15,7},
* 3
* / \
* 9 20
* / \
* 15 7
* return its bottom-up level order traversal as:
* [
* [3],
* [9,20],
* [15,7]
* ]
*
* @author dongyuxi
*
*/
public class Solution {
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> listlist = new ArrayList<ArrayList<Integer>>();
LinkedList<TreeNode> currentLevel = new LinkedList<TreeNode>();
int level = 0;
if (root != null)
currentLevel.add(root);
while (!currentLevel.isEmpty()) {
LinkedList<TreeNode> nextLevel = new LinkedList<TreeNode>();
ArrayList<Integer> list = new ArrayList<Integer>();
for (TreeNode node : currentLevel) {
list.add(node.val);
if (node.left != null)
nextLevel.add(node.left);
if (node.right != null)
nextLevel.add(node.right);
}
if (level % 2 == 1)
Collections.reverse(list);
listlist.add(list);
currentLevel = nextLevel;
level++;
}
return listlist;
}
}

支付宝 微信
文章目录