题目
二叉树的锯齿形层次遍历
给出一棵二叉树，返回其节点值的锯齿形层次遍历（先从左往右，下一层再从右往左，层与层之间交替进行）
样例
给出一棵二叉树 {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
返回其锯齿形的层次遍历为：
[
[3],
[20,9],
[15,7]
] 解题
交叉着走,受上面两题的影响，考虑用队列，发现不可以，换成栈，发现只用一个栈的话也不可以，（一个栈也能对71%的测试数据）在入栈 和出栈的时候，出现了混乱，考虑用两个栈。
下面是自己写的程序，代码写的好燋灼
关键点：两个栈交叉着进，交叉的出
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/ public class Solution {
/**
* @param root: The root of binary tree.
* @return: A list of lists of integer include
* the zigzag level order traversal of its nodes' values
*/
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
// write your code here
ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>>();
if(root == null)
return tree;
// rightstack 出栈序列是 左到右该层元素
Stack<TreeNode> leftstack = new Stack<TreeNode>();
leftstack.push(root); // leftstack 出栈序列是 右到左该层元素
Stack<TreeNode> rightstack = new Stack<TreeNode>();
boolean left = true;
while(!leftstack.empty() || !rightstack.empty()){
ArrayList<Integer> list = new ArrayList<Integer>();
if(left){
int size = leftstack.size();
for(int i=0;i<size;i++){
TreeNode node = leftstack.pop();
list.add(node.val);
if(node.left!=null)
rightstack.push(node.left);
if(node.right!=null)
rightstack.push(node.right); }
}else{
int size = rightstack.size();
for(int i=0;i<size;i++){
TreeNode node = rightstack.pop();
list.add(node.val);
if(node.right!=null)
leftstack.push(node.right);
if(node.left!=null)
leftstack.push(node.left); }
}
left=!left;
tree.add(list);
}
return tree;
}
}
Java Code
九章程序好像简洁了一些