從上到下按層列印二叉樹,同一層結點從左至右輸出。每一層輸出一行。
思路 層序周遊 隊列
每次列印一個節點的時候,如果該節點有子節點,則把該節點的子節點放到隊列的末尾,到隊列的頭部取出最早進入隊列的節點,
用到的資料結構
-
ArrayList<ArrayList> result = new ArrayList<ArrayList>();
用 ArrayList<ArrayList> 存最終結果,多對數組
-
Queue queue = new LinkedList();
用隊列 和連結清單來模拟層序周遊得到按順序的元素
-
ArrayList layerList = new ArrayList();
用 ArrayList 存每層的元素
5.13總結
這樣寫很便捷
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root==null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int count = queue.size();
List<Integer> list = new ArrayList<>();
while(count>0){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left!=null)
queue.add(node.left);
if(node.right!=null)
queue.add(node.right);
count--;
}
res.add(list);
}
return res;
}
}
層序周遊
層序周遊的模闆是用一個隊列,入隊每次遇到的非空結點,出隊目前最前結點,直到隊列為空,周遊完成
現在為了儲存層數資訊,我們添加了map,每次入隊新的結點,map 儲存 <結點,層數> 的 <K,V> 對
關于相同層數如何入 lists,前面也讨論這就不贅述了
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode root) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
if(root==null)
return lists;
HashMap<TreeNode, Integer> map = new HashMap<>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
//queue是抽象的不能被執行個體化,用LinkedList
queue.add(root);
map.put(root, 0);
while (!queue.isEmpty()) {
root = queue.poll();
int deep = map.get(root);
if (root.left != null) {
queue.add(root.left);
map.put(root.left, deep + 1);
}
if (root.right != null) {
queue.add(root.right);
map.put(root.right, deep + 1);
}
if (lists.size() <= deep) {
ArrayList<Integer> list = new ArrayList<>();
list.add(root.val);
lists.add(list);
} else {
ArrayList<Integer> list = lists.get(deep);
list.add(root.val);
}
}
return lists;
}
}
時間複雜度:O(n)O(n)
空間複雜度:O(n)O(n)
遞歸
好好思考
其實我們層序周遊一般不會用遞歸實作,但是這道題比較特殊,特殊之處在于,儲存層數的 deep 可以索引出對應的層資訊,友善結點直接找到同一層其他結點
我們考慮的問題就變成如何讓同一層結點從左到右依次列印,第一個要點肯定是保證入隊的順序,先左子樹,後右子樹,再一個要點是需要保證建立 list 的順序,即上一層的 list 先建立先存儲進 lists,綜合考慮,選用前序周遊的模闆
關于相同層數如何入 lists,前面也讨論這就不贅述了
//用遞歸做的
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
depth(pRoot, 0, list);
return list;
}
private void depth(TreeNode root, int depth, ArrayList<ArrayList<Integer>> list) {
if(root == null) return;
if(depth > =list.size())
list.add(new ArrayList<Integer>());
list.get(depth).add(root.val);
depth(root.left, depth + 1, list);
depth(root.right, depth + 1, list);
}
}