按之字顺序打印二叉树
题目描述
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
分析
较简单的做法是层级遍历,在偶数层时进行翻转。但效率不是很理想。
可以借助两个栈,分别存储奇偶行的节点,奇数行从左到右入栈。偶数行时依次从栈中取出节点,也就是上一层的从右到左了,这时再将偶数行从右到左加入栈供下一奇数行使用。
实现
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
int layer = 1;
//s1存奇数层节点
Stack<TreeNode> s1 = new Stack<TreeNode>();
s1.push(pRoot);
//s2存偶数层节点
Stack<TreeNode> s2 = new Stack<TreeNode>();
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
while (!s1.empty() || !s2.empty()) {
if (layer%2 != 0) {
ArrayList<Integer> temp = new ArrayList<Integer>();
while (!s1.empty()) {
TreeNode node = s1.pop();
if(node != null) {
temp.add(node.val);
System.out.print(node.val + " ");
s2.push(node.left);
s2.push(node.right);
}
}
if (!temp.isEmpty()) {
list.add(temp);
layer++;
System.out.println();
}
} else {
ArrayList<Integer> temp = new ArrayList<Integer>();
while (!s2.empty()) {
TreeNode node = s2.pop();
if(node != null) {
temp.add(node.val);
System.out.print(node.val + " ");
s1.push(node.right);
s1.push(node.left);
}
}
if (!temp.isEmpty()) {
list.add(temp);
layer++;
System.out.println();
}
}
}
return list;
}