二叉树按层遍历,利用队列,和last与nlast两个变量实现,last为本层中的最后一个节点,nlast为下一层的最后一个节点,每次从队列中出队元素,加入当前层的集合中,然后先将它的左子树入队(不为空的话),将nlast指向它,再将它的右子树入队(不为空的话),将nlast指向它,最后如果last跟它指向同一个节点,表示当前层已经到最后一个元素了,令last = nlast,将当前层集合加入结果集合中,建立新的层集合,如此循环,直到queue为空:
import java.util.ArrayDeque;
import java.util.ArrayList;
public class PrintBinaryTree {
public static void main(String[] args) {
TreeNode node1 = new TreeNode(3);
TreeNode node2 = new TreeNode(4);
TreeNode node3 = new TreeNode(5);
TreeNode node4 = new TreeNode(6);
TreeNode node5 = new TreeNode(7);
TreeNode node6 = new TreeNode(8);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node3.left = node5;
node3.right = node6;
int[][] res = printTree(node1);
for(int i = 0; i < res.length; i++) {
for(int j = 0; j < res[i].length; j++) {
System.out.print(res[i][j] + " ");
}
System.out.println();
}
}
public static int[][] printTree(TreeNode root) {
ArrayDeque<TreeNode> aq = new ArrayDeque<>();
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> index = new ArrayList<>();
TreeNode last = null;
TreeNode nlast = null;
TreeNode temp;
if(root == null)
return null;
else {
last = root;
aq.addLast(root);
}
while(aq.size() != 0) {
temp = aq.removeFirst();
index.add(temp.val);
if(temp.left != null) {
aq.addLast(temp.left);
nlast = temp.left;
}
if(temp.right != null) {
aq.addLast(temp.right);
nlast = temp.right;
}
if(temp == last) {
res.add(index);
index = new ArrayList<>();
last = nlast;
}
}
int result[][] = new int[res.size()][];
for(int i = 0; i < res.size(); i++) {
result[i] = new int[res.get(i).size()];
for(int j = 0; j < result[i].length; j++) {
result[i][j] = res.get(i).get(j);
}
}
return result;
}
}
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
结果
3
4 5
6 7 8