[LeetCode]Binary Zigzag Level Order Traversal

偶数层从左往右，奇数层从右往左，最后注意一下children的顺序就行。

代码如下：

iterative

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
	List<List<Integer>> res = new ArrayList<List<Integer>>();
	if (root == null)
	return res;
	int level = 0;
	LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
	queue.add(root);
	while (true) {
	res.add(new ArrayList<Integer>());
	int size = queue.size();
	for (int i = 0; i < size; i++) {
	TreeNode temp;
	if (level % 2 == 0) {
	temp = queue.removeFirst();
	if (temp.left != null)
	queue.addLast(temp.left);
	if (temp.right != null)
	queue.addLast(temp.right);
	} else {
	temp = queue.removeLast();
	if (temp.right != null)
	queue.addFirst(temp.right);
	if (temp.left != null)
	queue.addFirst(temp.left);
	}
	res.get(res.size() - 1).add(temp.val);
	}
	level++;
	if (queue.isEmpty())
	break;
	}
	return res;
	}
	}

view raw bst zigzag level order iterative.java hosted with ❤ by GitHub

recursive

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
	List<List<Integer>> res = new LinkedList<List<Integer>>();
	dfs(res, root, 1);
	return res;
	}
	public void dfs(List<List<Integer>> res, TreeNode node, int level) {
	if(node == null)
	return;
	if (res.size() < level)
	res.add(new LinkedList<Integer>());
	if (level % 2 != 0)
	res.get(level - 1).add(res.get(level - 1).size(), node.val);
	else
	res.get(level - 1).add(0, node.val);
	dfs(res, node.left, level + 1);
	dfs(res, node.right, level + 1);
	}
	}

view raw bst zigzag level order recursion.java hosted with ❤ by GitHub