题目描述
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
实现方法
1. 不同于普通的分层打印,这个需要从左到右和从右到左的方式交替进行,
那么我们就不能使用队列实现这个结果。
2. 从左到右和从右到左其实就是一个存储的方向问题,那么我们可以使用两个栈
交替存储实现,因为栈的后进先出的特性刚好可以实现这个交替打印的实现。
3. 具体实现过程:根据栈后进先出的特性,如果我们要从左到右打印,那么用一个名为rightT
oLeftStore的栈存储这一行,然后逐个取出打印就是从左向右,从右向左打印同理用一个名为l
eftToRightStore的栈进行处理
4. 打印的过程我们可以采用一个level控制,level=0表示打印奇数层,level=1表示打印偶数
层,然后将对应的存储栈数据取出,过程和分层遍历一样。
5. 但是在取出数据后,需要注意的是存储栈的左右子节点需要根据层的奇偶性判断,奇数节点
是从左往右存储在rightToLeftStore(奇数栈)中,从右往左的数据存储在leftToRightStore
(偶数栈)中,那么我们取出奇数层节点,其子节点就要按照先存储左子节点,再存储右子节
点到偶数栈中。类似的,从右往左打印时,子节点要按照先存储右子节点、再存储左子节点到奇数栈中实现。
java源码
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<ArrayList<Integer>> result = new ArrayList<>();
if (pRoot == null) return result;
ArrayList<Integer> temp = new ArrayList<>();
Stack<TreeNode> leftToRightStore = new Stack<>();
Stack<TreeNode> rightToLeftStore = new Stack<>();
int level = 0;
rightToLeftStore.push(pRoot);
while (!leftToRightStore.isEmpty() || !rightToLeftStore.isEmpty()) {
if (level == 0) {
//奇数层打印,从左往右
TreeNode current = rightToLeftStore.pop();
temp.add(current.val);
if (current.left != null) leftToRightStore.push(current.left);
if (current.right != null) leftToRightStore.push(current.right);
//判定这一层是否打印完,即栈空
if (rightToLeftStore.isEmpty()) {
level = 1;
result.add(new ArrayList(temp));
temp.clear();
}
} else {
//偶数层打印
TreeNode current = leftToRightStore.pop();
temp.add(current.val);
if (current.right != null) rightToLeftStore.push(current.right);
if (current.left != null) rightToLeftStore.push(current.left);
//判定这一层是否打印完,即栈空
if (leftToRightStore.isEmpty()) {
level = 0;
result.add(new ArrayList(temp));
temp.clear();
}
}
}
return result;
}
}
附上分层打印代码
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 {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (pRoot == null) return result;
ArrayList<Integer> temp = new ArrayList<>();
int toBePrint = 1;
int nextLevel = 0;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
temp.add(current.val);
toBePrint--;
if (current.left != null) {
queue.add(current.left);
nextLevel++;
}
if (current.right != null) {
queue.add(current.right);
nextLevel++;
}
if (toBePrint == 0) {
result.add(new ArrayList(temp));
temp.clear();
toBePrint = nextLevel;
nextLevel = 0;
}
}
return result;
}
}
网友评论