按之字形顺序打印二叉树

题目

请实现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);
}

}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 按之字形顺序打印二叉树

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡