1，BFS打印
二叉树的BFS打印，就是一层一层的往下打印，就像下面这样
具体可以看下373，数据结构-6,树，这里介绍了递归和非递归的解法。非递归的代码如下
public static void levelOrder(TreeNode tree) {
if (tree == null)
return;
Queue<treenode> queue = new LinkedList<>();
queue.add(tree);//相当于把数据加入到队列尾部
while (!queue.isEmpty()) {
//poll方法相当于移除队列头部的元素
TreeNode node = queue.poll();
System.out.println(node.val);
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
}
因为上面每次都是从左边开始打印，但这题要求的是先从左边，下一层从右边，在下一次从左边……左右交替的。我们可以使用一个变量leftToRight，如果是true就表示从左边开始打印，否则就从右边开始打印，只需要把上面代码修改下即可，来看下
public ArrayList<arraylist<integer>> zigzagLevelOrder(TreeNode root) {
ArrayList<arraylist<integer>> res = new ArrayList<>();
if (root == null)
return res;
//创建队列，保存节点
Queue<treenode> queue = new LinkedList<>();
queue.add(root);//先把节点加入到队列中
boolean leftToRight = true;//第一步先从左边开始打印
while (!queue.isEmpty()) {
//记录每层节点的值
ArrayList<integer> level = new ArrayList<>();
//统计这一层有多少个节点
int count = queue.size();
//遍历这一层的所有节点，把他们全部从队列中移出来，顺便
//把他们的值加入到集合level中，接着再把他们的子节点（如果有）
//加入到队列中
for (int i = 0; i < count; i++) {
//poll移除队列头部元素（队列在头部移除，尾部添加）
TreeNode node = queue.poll();
//判断是从左往右打印还是从右往左打印。
if (leftToRight) {
//如果从左边打印，直接把访问的节点值加入到列表level的末尾即可
level.add(node.val);
} else {
//如果是从右边开始打印，每次要把访问的节点值
//加入到列表的最前面
level.add(0, node.val);
}
//左右子节点如果不为空会被加入到队列中
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
//把这一层的节点值加入到集合res中
res.add(level);
//改变下次访问的方向
leftToRight = !leftToRight;
}
return res;
}
2，DFS打印
这题除了使用BFS以外，还可以使用DFS，也可以参照373，数据结构-6,树中二叉树的BFS遍历的递归解法，稍作修改。但这里要有个判断，如果走到下一层的时候集合没有创建，要先创建下一层的集合，代码也很简单，我们来看下。
public ArrayList<arraylist<integer>> zigzagLevelOrder(TreeNode root) {
ArrayList<arraylist<integer>> res = new ArrayList<>();
travel(root, res, 0);
return res;
}
private void travel(TreeNode cur, ArrayList<arraylist<integer>> res, int level) {
if (cur == null)
return;
//如果res.size() <= level说明下一层的集合还没创建，所以要先创建下一层的集合
if (res.size() <= level) {
ArrayList<integer> newLevel = new ArrayList<>();
res.add(newLevel);
}
//遍历到第几层我们就操作第几层的数据
List<integer> list = res.get(level);
//这里默认根节点是第0层，偶数层相当于从左往右遍历，
// 所以要添加到集合的末尾，如果是奇数层相当于从右往左遍历，
// 要把数据添加到集合的开头
if (level % 2 == 0)
list.add(cur.val);
else
list.add(0, cur.val);
//分别遍历左右两个子节点，到下一层了，所以层数要加1
travel(cur.left, res, level + 1);
travel(cur.right, res, level + 1);
}
京公网安备 11010502036488号