題目描述

給你二叉樹的根節點 root，返回其節點值的層序遍歷（即逐層地，從左到右訪問所有節點）。

解題思路

使用 BFS（廣度優先搜索）的思想，維護當前層的所有節點，逐層處理：

1. 將根節點加入當前層節點列表
2. 遍歷當前層所有節點，收集它們的值
3. 收集當前層所有節點的子節點作為下一層
4. 重復步驟2-3直到沒有下一層

核心代碼

public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}List<TreeNode> currentRowNodeList = new ArrayList<>();currentRowNodeList.add(root);while (true) {// 收集當前層的值List<Integer> currentRowValList = new ArrayList<>();for (TreeNode node : currentRowNodeList) {currentRowValList.add(node.val);}result.add(currentRowValList);// 收集下一層節點List<TreeNode> nextNodeList = new ArrayList<>();for (TreeNode treeNode : currentRowNodeList) {if (treeNode.left != null) {nextNodeList.add(treeNode.left);}if (treeNode.right != null) {nextNodeList.add(treeNode.right);}}if (nextNodeList.isEmpty()) {break;}currentRowNodeList = nextNodeList;}return result;
}

復雜度分析

• 時間復雜度: O(n)，n 為二叉樹節點數，每個節點訪問一次
• 空間復雜度: O(n)，最壞情況下需要存儲一層的所有節點

示例驗證

輸入：[3,9,20,null,null,15,7]
輸出：[[3],[9,20],[15,7]]

算法按層級正確遍歷，符合預期結果。