请实现1个函数依照之字形打印2叉树，即第1行依照从左到右的顺序打印，第2层依照从右至左的顺序打印，第3行依照从左到右的顺序打印，其他行以此类推。
层次遍历2叉树很好理解
用队列临时寄存其中1层的结点，出队列更新到下1层结点
按之字形顺序打印2叉树需要两个栈。
在打印某1行结点时，把下1层的结点保存到相应的栈里。如果当前打印的是奇数层，则先保存左子结点再保存右子结点到第1个栈里；如果当前打印的是偶数层，则先保存右结点在保存左子结点到第2个栈里。
import java.util.ArrayList;
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<Integer> row = new ArrayList<Integer>();
ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
if(pRoot == null)
return result;
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
boolean flag = true;
stack1.push(pRoot);
while(!stack1.isEmpty() || !stack2.isEmpty()){
row = new ArrayList<Integer>();
if(flag){
int size = stack1.size();
while((size--) >0){
TreeNode node = stack1.pop();
row.add(node.val);
if(node.left!=null)
stack2.push(node.left);
if(node.right!=null)
stack2.push(node.right);
}
flag = false;
}else{
int size = stack2.size();
while((size--) >0){
TreeNode node = stack2.pop();
row.add(node.val);
if(node.right!=null)
stack1.push(node.right);
if(node.left!=null)
stack1.push(node.left);
}
flag = true;
}
result.add(row);
}
return result;
}
}if else 程序写的很搓
用队列
层次遍历输出的每层元素都是左右的
对本题我们需要交叉的输出
左右输出
右左输出
所有只需要对偶数的行在层次遍历的基础上进行逆序就行了
import java.util.ArrayList;
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<Integer> row = new ArrayList<Integer>();
ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
if(pRoot == null)
return result;
boolean flag = true;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(pRoot);
while(!queue.isEmpty()){
int size = queue.size();
row = new ArrayList<Integer>();
while((size--)>0){
TreeNode node = queue.poll();
row.add(node.val);
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
}
if(!flag){
reverse(row);
}
flag = !flag;
result.add(row);
}
return result;
}
public void reverse(ArrayList<Integer> list){
int i=0;
int j=list.size() -1;
while(i<j){
swap(list,i,j);
i++;
j--;
}
}
public void swap(ArrayList<Integer> list,int i,int j){
int a = list.get(i);
int b = list.get(j);
list.set(i,b);
list.set(j,a);
}
}