原题
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7] ]
解法
思想
用两个栈来交替存储某一层和下一层的节点:
读取第一个栈的时候，从左向右的读取节点，将它们的子节点从左向右入第二个栈，能使读取第二个栈的时候是以从右向左的顺序出栈的。
读取第二个栈的时候，从右向左的读取节点，将它们的子节点从右向左入第一个栈，能使读取第一个栈的时候是以从左向右的顺序出栈的。
这样交替使用两个栈，可以实现两层之间的顺序反转。
代码
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
Stack<TreeNode> first = new Stack<>();
Stack<TreeNode> second = new Stack<>();
List<Integer> cur;
if(root == null) return ans;
first.push(root);
while(!first.isEmpty()||!second.isEmpty()){
//当前层的节点按从左向右的顺序依次出栈，子节点按从左向右的顺序入second栈，实现顺序逆转
cur = new ArrayList<>();
while(!first.isEmpty()){
TreeNode node = first.pop();
cur.add(node.val);
if(node.left!=null) second.push(node.left);
if(node.right!=null) second.push(node.right);
}
ans.add(cur);
//下一层的节点按从右向左的顺序依次出栈，子节点按从右向左的顺序入first栈，实现顺序逆转
if(second.isEmpty()) break;
cur = new ArrayList<>();
while(!second.isEmpty()){
TreeNode node = second.pop();
cur.add(node.val);
if(node.right!=null) first.push(node.right);
if(node.left!=null) first.push(node.left);
}
ans.add(cur);
}
return ans;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode103-%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e9%94%af%e9%bd%bf%e5%bd%a2%e5%b1%82%e6%ac%a1%e9%81%8d%e5%8e%86/
