描述
給出一棵二叉樹膊毁，返回其節(jié)點(diǎn)值的層次遍歷（逐層從左往右訪問）
樣例
給一棵二叉樹 {3,9,20,#,#,15,7} ：
3
/ \
9 20
/ \
15 7
返回他的分層遍歷結(jié)果：
[
[3],
[9,20],
[15,7]
]
挑戰(zhàn)
挑戰(zhàn)1：只使用一個(gè)隊(duì)列去實(shí)現(xiàn)它
挑戰(zhàn)2：用DFS算法來(lái)做
說(shuō)明
用隊(duì)列來(lái)做BFS時(shí)，無(wú)論寫不寫分層代碼本質(zhì)上都是一層層進(jìn)出隊(duì)列砾隅，只是寫了分層代碼可以在每一層結(jié)束時(shí)將本層全部結(jié)點(diǎn)保存到動(dòng)態(tài)數(shù)組格嗅，可以在輸出上體現(xiàn)每一層都有哪些
代碼
/**
* 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每次都會(huì)new一個(gè)新的
result.add(level);
}
return result;
}
}
注意
1.當(dāng)root為空時(shí)式散，不能返回null（會(huì)報(bào)錯(cuò)）汉匙，應(yīng)該返回一個(gè)空的result
2.隊(duì)列用linkedlist形式這樣更加方便bst運(yùn)行時(shí)隨時(shí)添加節(jié)點(diǎn)涤姊，節(jié)省開銷
關(guān)鍵點(diǎn)
理解此算法的關(guān)鍵在于理解size代表當(dāng)前層的長(zhǎng)度镣衡，是在每一層節(jié)點(diǎn)全部遍歷完后才進(jìn)行更新的霜定，在size未更新階段for循環(huán)進(jìn)行作用档悠，遍歷層中每一節(jié)點(diǎn)，分別將它們的子節(jié)點(diǎn)全部加入隊(duì)列中去望浩，遍歷完一層節(jié)點(diǎn)后辖所，由while循環(huán)判斷下隊(duì)列是否為空（即有沒有將全部節(jié)點(diǎn)添加到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;
}
}