題目連結

題型解說

這是一題難度為簡單的題目

需要設計一個方法，此方法會傳入一個二元樹 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;
    }
}