題型解說
這是一題難度為簡單的題目
需要設計一個方法,此方法會傳入一個二元樹 root
將這顆樹每一層的節點收集後回傳
解題思路
這題也是沒什麼難點,看是要用遞迴還是迴圈都可以解題
LeetCode 上有很多的題目都跟樹有關的,基本歷遍樹的方法掌握之後,解題上都不會太困難
程式碼
Java
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
levelOrderBottom(root, 1, result);
Collections.reverse(result);
return result;
}
public void levelOrderBottom(TreeNode root, int nowLevel, List<List<Integer>> list) {
if (root == null) {
return;
}
// 與迴圈版本不同,需要檢查有沒有建立當前層級的 list
if (list.size() < nowLevel) {
list.add(new ArrayList<>());
}
levelOrderBottom(root.left, nowLevel +1, list);
levelOrderBottom(root.right, nowLevel +1, list);
list.get(nowLevel -1).add(root.val);
}
}
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue queue = new LinkedList();
queue.offer(root);
while (!queue.isEmpty()) {
result.add(new ArrayList<>()); // 每一次 while 循環都代表是新的一層
for (int i = queue.size(); i > 0; i--) {
TreeNode temp = (TreeNode)queue.poll();
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
result.get(result.size() -1).add(temp.val);
}
}
Collections.reverse(result); // 將 list 反轉
return result;
}
}