剑指Offer:树的层次遍历，分层打印和按之字型打印
1.把二叉树打印成多行
题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
如：
1
2，3
3，4，5
解题：层次遍历使用队列，这里维护两个队列进行的区分cur，next，分别存储当前行节点和下一行节点，遍历完当前行cur后，两个队列再进行交换。
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
if(pRoot==null)
return res;
Queue<TreeNode> cur=new LinkedList<>();
Queue<TreeNode> next=new LinkedList<>();
cur.offer(pRoot);
ArrayList<Integer> list=new ArrayList<>();
while(!cur.isEmpty()){
TreeNode pNode=cur.poll();
list.add(pNode.val);
if(pNode.left!=null)
next.offer(pNode.left);
if(pNode.right!=null)
next.offer(pNode.right);
if(cur.isEmpty()){
Queue<TreeNode> tmp=cur;
cur=next;
next=tmp;
res.add(list);
list=new ArrayList<>();
}
}
return res;
}如果不使用两个队列，就需要两个变量last,nlast，分别指向当前行的最后一个节点，和下一行的最后一个节点。如果访问的节点是当前行的最后一个节点last就表示当前行访问结束。
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
if(pRoot==null)
return res;
Queue<TreeNode> q=new LinkedList<>();
q.offer(pRoot);
TreeNode last=pRoot,nlast=pRoot;
ArrayList<Integer> list=new ArrayList<>();
while(!q.isEmpty()){
TreeNode pNode=q.poll();
list.add(pNode.val);
if(pNode.left!=null){
q.offer(pNode.left);
nlast=pNode.left;
}
if(pNode.right!=null){
q.offer(pNode.right);
nlast=pNode.right;
}
if(pNode==last){
last=nlast;
res.add(list);
list=new ArrayList<>();
}
}
return res;
}
2. 按之字形顺序打印二叉树
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
如
1
3，2
4 ，5， 6， 7
这到题还是层次遍历，但遍历一层过后，遍历的顺序要相反，所以使用两个栈来当前层的节点和下一层的节点，但要注意根据访问的顺序是从左到右，还是从右到左，决定先访问左节点还是右节点。
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
Stack<TreeNode> cur=new Stack<>();
Stack<TreeNode> rev=new Stack<>();
cur.push(pRoot);
int flag=0;
ArrayList<Integer> list=new ArrayList<Integer>();
while(!cur.isEmpty()){
TreeNode pNode=cur.pop();
list.add(pNode.val);
if(flag==0){
if(pNode.left!=null)
rev.push(pNode.left);
if(pNode.right!=null)
rev.push(pNode.right);
}else if(flag!=0){
if(pNode.right!=null)
rev.push(pNode.right);
if(pNode.left!=null)
rev.push(pNode.left);
}
if(cur.isEmpty()){
Stack<TreeNode> tmp=cur;
cur=rev;
rev=tmp;
flag=1-flag;
res.add(list);
list=new ArrayList<Integer>();
}
}
return res;
}
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。