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

<p>给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。</p>

<p>例如：<br />
给定二叉树 <code>[3,9,20,null,null,15,7]</code>,</p>

<pre>
    3
   / \
  9  20
    /  \
   15   7
</pre>

<p>返回锯齿形层序遍历如下：</p>

<pre>
[
  [3],
  [20,9],
  [15,7]
]
</pre>


## template

```java

public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

class Solution {
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> list = new LinkedList<>();
		if (root == null) {
			return list;
		}
		Stack<TreeNode> stack1 = new Stack<>();
		stack1.push(root);

		boolean postive = true;

		while (!stack1.isEmpty()) {
			Stack<TreeNode> stack2 = new Stack<>();
			List<Integer> subList = new LinkedList<>();
			while (!stack1.isEmpty()) {
				TreeNode current = stack1.pop();
				subList.add(current.val);
				if (postive) {
					if (current.left != null) {
						stack2.push(current.left);
					}
					if (current.right != null) {
						stack2.push(current.right);
					}
				} else {
					if (current.right != null) {
						stack2.push(current.right);
					}
					if (current.left != null) {
						stack2.push(current.left);
					}
				}

			}
			postive = !postive;

			stack1 = stack2;
			list.add(subList);
		}

		return list;

	}
}


```

## 答案

```java

```

## 选项

### A

```java

```

### B

```java

```

### C

```java

```