面试题32.3：之字形打印二叉树
题目要求：
请实现一个函数按照之字形打印二叉树。即第一层从左到右打印，第二层从右到左打印，第三层继续从左到右，以此类推。
解题思路：
第k行从左到右打印，第k+1行从右到左打印，可以比较容易想到用两个栈来实现。
另外要注意，根据是从左到右还是从右到左访问的不同，压入左右子节点的顺序也有所不同。
package structure;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created by ryder on 2017/6/12.
* 树节点
*/
public class TreeNode<T> {
public T val;
public TreeNode<T> left;
public TreeNode<T> right;
public TreeNode(T val){
this.val = val;
this.left = null;
this.right = null;
}
}
package chapter4;
import structure.TreeNode;
import java.util.Stack;
/**
* Created by ryder on 2017/7/18.
* 之字形打印二叉树
*/
public class P176_printTreeInSpecial {
public static void printTreeInSpeical(TreeNode<Integer> root){
if(root==null)
return;
Stack<TreeNode<Integer>> stack1 = new Stack<>();
Stack<TreeNode<Integer>> stack2 = new Stack<>();
TreeNode<Integer> temp;
stack1.push(root);
while(!stack1.isEmpty() || !stack2.isEmpty()){
if(!stack1.isEmpty()) {
while (!stack1.isEmpty()) {
temp = stack1.pop();
System.out.print(temp.val);
System.out.print('\t');
if (temp.left != null)
stack2.push(temp.left);
if (temp.right != null)
stack2.push(temp.right);
}
}
else {
while (!stack2.isEmpty()) {
temp = stack2.pop();
System.out.print(temp.val);
System.out.print('\t');
if (temp.right != null)
stack1.push(temp.right);
if (temp.left != null)
stack1.push(temp.left);
}
}
System.out.println();
}
}
public static void main(String[] args){
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
TreeNode<Integer> root = new TreeNode<Integer>(1);
root.left = new TreeNode<Integer>(2);
root.right = new TreeNode<Integer>(3);
root.left.left = new TreeNode<Integer>(4);
root.left.right = new TreeNode<Integer>(5);
root.right.left = new TreeNode<Integer>(6);
root.right.right = new TreeNode<Integer>(7);
printTreeInSpeical(root);
}
}
运行结果
1111
