按之字形顺序打印二叉树

时间:2022-08-29 17:28:07

题目

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

解题

层次遍历二叉树很好理解
用队列临时存放其中一层的结点,出队列更新到下一层结点
按之字形顺序打印二叉树需要两个栈。
在打印某一行结点时,把下一层的结点保存到相应的栈里。如果当前打印的是奇数层,则先保存左子结点再保存右子结点到第一个栈里;如果当前打印的是偶数层,则先保存右结点在保存左子结点到第二个栈里。

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);
}

}