题目描述
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
思路:
1、实现之字形打印二叉树,需要对每一层的结点进行分类,同时其打印的顺序也是需要从左往右、或者从右往左都是需要根据其具体的层数进行判断的;
2、对于在每次出栈或者入栈的时候,需要对栈进行判断,对结点是否具有子节点进行判断,否则得到的ArrayList会有[ ];
3、注意在栈中操作的是结点,在ArrayList中操作的是结点的值val;
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> list =new ArrayList<ArrayList<Integer> >();
if(pRoot==null) return list;
Stack<TreeNode> s1=new Stack<TreeNode>();
Stack<TreeNode> s2=new Stack<TreeNode>();
s1.push(pRoot);
int count=1;
while(!s1.empty() || !s2.empty()){
if(count%2!=0){
ArrayList<Integer> arr=new ArrayList<Integer>();
while(!s1.empty()){
TreeNode node=s1.pop();
if(node != null) {
arr.add(node.val);
s2.push(node.left);
s2.push(node.right);
}
}
if (!arr.isEmpty()) {
list.add(arr);
count++;
}
}else{
ArrayList<Integer> arr=new ArrayList<Integer>();
while(!s2.empty()){
TreeNode node=s2.pop();
if(node != null) {
arr.add(node.val);
s1.push(node.right);
s1.push(node.left);
}
}
if (!arr.isEmpty()) {
list.add(arr);
count++;
}
}
}
return list;
}
}