NC15 求二叉树的层序遍历 考过的企业 - 小米
题目描述
给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
img
该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]
考察关键点
- 二叉树的层序遍历，用广度优先搜索（BFS），广度优先搜索使用队列来实现
- 该题目的返回结果要求返回结果中包含层信息，思考如何在BFS中融合如层序信息
解题思路
-
如果不考虑层序信息，BFS可以很简单的使用一个队列实现，如下代码是按照层序打印遍历结果
public void levelOrder(TreeNode root) { LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode top = queue.pop(); System.out.println(top.val); if (top.left != null) { queue.add(top.left); } if (top.right != null) { queue.add(top.right); } } }
-
上面代码简单BFS已经让我们获取到了层序的遍历结果，但是此处还不包含打印的节点在二叉树的哪一层的信息，那我们尝试修改上述代码来增加层数信息。这里我们尝试在这个
while循环上做做文章，若每次while循环只处理同一层的节点，并在循环中把这一层所有节点的值放入一个列表中存入结果集，那么就可以求出题目要求的结果，那么现在这个问题就变成，如何保证一次while循环只处理二叉树一层的节点呢？这里我们再回到帮助我们进行BFS的队列，如果我们能保证每次开始一次while循环时，队列里只有同一层的数据，并且处理完这一层所有的数据后，再进入下一次循环，那么这个问题就解决了，OK，直接看代码。public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> ret = new ArrayList<>(); if (root == null) { return ret; } // 用于BFS的队列 LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int len = queue.size(); // 初始化同一层的数组 ret.add(new ArrayList<>()); // 进入while循环时，队列中都是同一层的节点，并且在本次while循环中将这一层的所有节点处理完，所以这里取一开始进入循环时的队列长度，并取出同一层所有的节点放入结果集 for (int i = 0; i < len; i++) { TreeNode top = queue.pop(); // 放入这一层对应的数组中 ret.get(ret.size() - 1).add(first.val); System.out.println(top.val); // 将下一层的节点放入队列，准备进行下一次while循环 if (top.left != null) { queue.add(top.left); } if (top.right != null) { queue.add(top.right); } } } return ret; }
完整代码
package NC15;
import java.util.*;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class NC15 {
/**
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
if (root == null) {
return ret;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int len = queue.size();
ret.add(new ArrayList<>());
for (int i = 0; i < len; i++) {
TreeNode top = queue.pop();
ret.get(ret.size() - 1).add(first.val);
System.out.println(top.val);
if (top.left != null) {
queue.add(top.left);
}
if (top.right != null) {
queue.add(top.right);
}
}
}
return ret;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(3, new TreeNode(9, new TreeNode(15, null, null), new TreeNode(7, null, null)), new TreeNode(20, null, null));
System.out.println(levelOrder(root));
}
}
