[LeetCode 103]Binary Tree Zigzag Level Order Traversal

题目链接：binary-tree-zigzag-level-order-traversal

类似的题型：

1 Binary Tree Level Order Traversal

2Binary Tree Level Order Traversal II

3Minimum Depth of Binary Tree

4Sum Root to Leaf Numbers

5[LeetCode 101] Symmetric Tree

import java.util.ArrayList;import java.util.List;/** * 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 7return its zigzag level order traversal as:[[3],[20,9],[15,7]] * */public class BinaryTreeZigzagLevelOrderTraversal {public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}}//33 / 33 test cases passed.//Status: Accepted//Runtime: 236 ms//Submitted: 0 minutes ago//层次遍历法public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<TreeNode> stack = new ArrayList<TreeNode>();List<List<Integer>> zigzags = new ArrayList<List<Integer>>();int level = 0;if(root == null) {return zigzags;}stack.add(root);while(!stack.isEmpty()) {List<Integer> zigzig = new ArrayList<Integer>();int size = stack.size();level ++;for (int i = 0; i < size; i++) {TreeNode node = stack.remove(0);if(node.left != null) {stack.add(node.left);}if(node.right != null) {stack.add(node.right);}if(level % 2 == 1) {zigzig.add(node.val);} else {zigzig.add(0, node.val);}}zigzags.add(zigzig);}return zigzags;}public static void main(String[] args) {// TODO Auto-generated method stub}}

，没有什么可凭仗，只有他的好身体，没有地方可去，只想到处流浪。