描述
给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）
样例
给一棵二叉树 {3,9,20,#,#,15,7} ：
3
/ \
9 20
/ \
15 7
返回他的分层遍历结果：
[
[3],
[9,20],
[15,7]
]
挑战
挑战1：只使用一个队列去实现它
挑战2：用DFS算法来做
说明
用队列来做BFS时，无论写不写分层代码本质上都是一层层进出队列，只是写了分层代码可以在每一层结束时将本层全部结点保存到动态数组，可以在输出上体现每一层都有哪些
代码
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
- BST
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List result = new ArrayList();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
ArrayList<Integer> level = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode head = queue.poll();
level.add(head.val);
if (head.left != null) {
queue.offer(head.left);
}
if(head.right != null) {
queue.offer(head.right);
}
}
// 此处level不需要deep copy,while每次都会new一个新的
result.add(level);
}
return result;
}
}
注意
1.当root为空时，不能返回null（会报错），应该返回一个空的result
2.队列用linkedlist形式这样更加方便bst运行时随时添加节点，节省开销
关键点
理解此算法的关键在于理解size代表当前层的长度，是在每一层节点全部遍历完后才进行更新的，在size未更新阶段for循环进行作用，遍历层中每一节点，分别将它们的子节点全部加入队列中去，遍历完一层节点后，由while循环判断下队列是否为空（即有没有将全部节点添加到level中去）, 如果不需要分层，将while后面三行去掉
- DFS
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return results;
}
int maxLevel = 0;
while (true) {
ArrayList<Integer> level = new ArrayList<Integer>();
dfs(root, level, 0, maxLevel);
if (level.size() == 0) {
break;
}
results.add(level);
maxLevel++;
}
return results;
}
private void dfs(TreeNode root,
ArrayList<Integer> level,
int curtLevel,
int maxLevel) {
if (root == null || curtLevel > maxLevel) {
return;
}
if (curtLevel == maxLevel) {
level.add(root.val);
return;
}
dfs(root.left, level, curtLevel + 1, maxLevel);
dfs(root.right, level, curtLevel + 1, maxLevel);
}
}
- BFS. two queues
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return result;
}
ArrayList<TreeNode> Q1 = new ArrayList<TreeNode>();
ArrayList<TreeNode> Q2 = new ArrayList<TreeNode>();
Q1.add(root);
while (Q1.size() != 0) {
ArrayList<Integer> level = new ArrayList<Integer>();
Q2.clear();
for (int i = 0; i < Q1.size(); i++) {
TreeNode node = Q1.get(i);
level.add(node.val);
if (node.left != null) {
Q2.add(node.left);
}
if (node.right != null) {
Q2.add(node.right);
}
}
// swap q1 and q2
ArrayList<TreeNode> temp = Q1;
Q1 = Q2;
Q2 = temp;
// add to result
result.add(level);
}
return result;
}
}
- BFS, queue with dummy node
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return result;
}
Queue<TreeNode> Q = new LinkedList<TreeNode>();
Q.offer(root);
Q.offer(null); // dummy node
ArrayList<Integer> level = new ArrayList<Integer>();
while (!Q.isEmpty()) {
TreeNode node = Q.poll();
if (node == null) {
if (level.size() == 0) {
break;
}
result.add(level);
level = new ArrayList<Integer>();
Q.offer(null); // add a new dummy node
continue;
}
level.add(node.val);
if (node.left != null) {
Q.offer(node.left);
}
if (node.right != null) {
Q.offer(node.right);
}
}
return result;
}
}