T103. Binary Tree Zigzag Level Order Traversal【Medium】
题目
给定一个二叉树，按 Z 子顺序返回其节点的值。 （即从左到右，然后从右到左，然后再从左到右这样）。
举个例子：
给出二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回：
[
[3],
[20,9],
[15,7]
]
思路
思路就是往下添加时，偶数从左往右添加，奇数从右往左添加。（从 0 层开始）
从右往左添加：
LinkedList.add(0, curr.val);
代码
代码取自 Top Solution，稍作注释
public List<List<Integer>> zigzagLevelOrder(TreeNode root)
{
List<List<Integer>> sol = new ArrayList<>();
travel(root, sol, 0);
return sol;
}
private void travel(TreeNode curr, List<List<Integer>> sol, int level)
{
// 若是空的树，返回null
if(curr == null) return;
// 随着深度的增加添加链表
if(sol.size() <= level)
{
List<Integer> newLevel = new LinkedList<>();
sol.add(newLevel);
}
// 得到当前数组
List<Integer> collection = sol.get(level);
// 偶数从左往右，奇数从右往左
if(level % 2 == 0) collection.add(curr.val);
else collection.add(0, curr.val);
// 递归遍历左右节点
travel(curr.left, sol, level + 1);
travel(curr.right, sol, level + 1);
}
