题目描述
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
由题意我们可以知道,打印结果应该为:
A
C、B
D、E、F、G
我们可以先将第一行A保存在一个数据容器中;
然后根据第一行依次得到第二行C、B并将其放入一个数组容器;
根据第二行得到第三行D、E、F、G时先得到的为D,而D为B的子节点,B在第二行是最后放入的却最先被第三行使用,这种后入先出的特点正好符合栈的特点。
于是我们可以使用两个栈来分别保存第奇数行和第偶数行。
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
//第奇数行,里面顺序为从左向右
Stack<TreeNode> stackLeft = new Stack<TreeNode>();
Stack<TreeNode> stackRight = new Stack<TreeNode>();
ArrayList<Integer> newLine = new ArrayList<Integer>();
TreeNode current = null;
if(pRoot == null) {
return res;
}
//第偶数行,里面顺序为从右向左
newLine.add(pRoot.val);
res.add(newLine);
stackLeft.push(pRoot);
while(!(stackLeft.isEmpty() && stackRight.isEmpty())) {
//遍历奇数行
if(!stackLeft.isEmpty()) {
newLine = new ArrayList<Integer>();
while(!stackLeft.isEmpty()) {
current = stackLeft.pop();
if(current.right != null) {
stackRight.push(current.right);
newLine.add(current.right.val);
}
if(current.left != null) {
stackRight.push(current.left);
newLine.add(current.left.val);
}
}
if(newLine.size() != 0) {
res.add(newLine);
}
}
//遍历偶数行
if(!stackRight.isEmpty()) {
newLine = new ArrayList<Integer>();
while(!stackRight.isEmpty()) {
current = stackRight.pop();
if(current.left != null) {
stackLeft.push(current.left);
newLine.add(current.left.val);
}
if(current.right != null) {
stackLeft.push(current.right);
newLine.add(current.right.val);
}
}
if(newLine.size() != 0) {
res.add(newLine);
}
}
}
return res;
}
}
解法二:
使用队列,今天懒得写了,之后补上