102. Binary Tree Level Order Traversal - Medium

前往題目

之前寫過了，搬運一下

想法

• 這題居然沒想到用BFS，看來我又忘了它的存在

思路

• 用BFS

Code

public List<List<Integer>> levelOrder(TreeNode root) {
    // Queue for processing
    Queue<TreeNode> q = new LinkedList<>();
    
    // Init. by root node
    q.add(root);

    // Result list
    List<List<Integer>> res = new LinkedList<>();

    if (root == null) return res;

    // Process all elements of the queue
    while (!q.isEmpty()) {
        int size = q.size();

        List<Integer> tempList = new LinkedList<>();

        for (int i = 0; i < size; ++i) {
            TreeNode currNode = q.poll();

            if (currNode != null) {
                tempList.add(currNode.val);
                // Add its children
                for (int j = 0; j < 2; ++j) {
                    TreeNode childNode = (j == 0) ? currNode.left : currNode.right;
                    if (null != childNode) {
                        q.add(childNode);
                    }
                }
            }
        }

        // Add to the result
        res.add(tempList);
    }

    return res;
}

2024/01/07

• 靠自己10分鐘寫出來了😭跟原本的code有一點點差異，覺得比較好理解一點
• 覺得原本的code加入子樹時候的邏輯有點繞，這次寫的直接判斷是否null直接加入就可以了，沒有多餘的邏輯

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        
        // 沒有node
        if (root == null) {
            return res;
        }
        // 只有一個node
        if (root.left == null && root.right == null) {
            res.add(new LinkedList<Integer>(Arrays.asList(root.val)));
            return res;
        }

        Queue<TreeNode> q = new LinkedList();

        // 先加入root
        q.offer(root);

        // 開始BFS
        while (!q.isEmpty()) {
            int qSize = q.size();

            List<Integer> levelList = new LinkedList();

            for (int i = 0; i < qSize; ++i) {
                TreeNode curNode = q.poll();
                // 加入這層的list
                levelList.add(curNode.val);
                // 加入左子樹
                if (curNode.left != null) {
                    q.offer(curNode.left);
                }
                // 加入右子樹
                if (curNode.right != null) {
                    q.offer(curNode.right);
                }
            }
            // 把這層的list加到答案裡
            res.add(levelList);
        }
        return res;
    }
}