二叉樹的層序遍歷是一種經典的遍歷方式，它要求按層級逐層訪問二叉樹的節點。通常我們會使用隊列來實現層序遍歷，但遞歸法也是一種可行且有趣的思路。本文將深入探討遞歸法解決二叉樹層序遍歷的核心難點，并結合代碼和模擬過程進行詳細講解。
一、題目描述
給定一個二叉樹的根節點 root，返回其節點值的層序遍歷結果，即逐層遍歷，從左到右訪問所有節點。例如，輸入二叉樹：
3/ \9 20/ \15 7
輸出結果應為：
[[3], [9, 20], [15, 7]]。
二、核心難點分析
難點1：臨時數組的創建邏輯
在遞歸法中，我們需要預先創建好數組來存儲每一層的節點值。這里的關鍵是如何根據當前節點的深度（層級）來確定將節點值存儲到哪個數組中。
- 深度標記：
我們使用一個變量deep來表示當前節點所在的深度。初始時，根節點的深度為1。 - 數組創建與填充：
在遞歸過程中，每當遇到一個新的深度deep時，我們需要確保res中已經有足夠的子列表來存儲該層的節點值。如果res的大小小于deep，則創建一個新的空列表并添加到res中。然后，將當前節點的值添加到res中對應深度的子列表中。
難點2：遞歸的具體邏輯實現
遞歸法的核心在于如何通過遞歸調用自身來遍歷二叉樹的每一層。
- 遞歸終止條件：
當遇到null節點時，遞歸結束。這是因為null節點沒有值，也沒有子節點，不需要進行任何處理。 - 遞歸調用：
對于每個非null節點，我們先將其值添加到對應深度的子列表中，然后分別對其左子節點和右子節點進行遞歸調用。在遞歸調用時，深度deep需要加1，以表示進入了下一層。
三、解題思路分步解析
步驟1：初始化結果列表和遞歸調用
public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();levelOrderBFS(res, root, 0);return res;
}
這里我們首先創建了一個空的結果列表 res，然后調用遞歸函數 levelOrderBFS 開始遍歷。初始深度設為 0，因為在遞歸函數內部會先將深度加 1 再進行處理。
步驟2：遞歸函數實現
public void levelOrderBFS(List<List<Integer>> res, TreeNode root, int deep) {if (root == null) {return;}deep++;while (res.size() < deep) {List<Integer> resList = new ArrayList<>();res.add(resList);}res.get(deep - 1).add(root.val);levelOrderBFS(res, root.left, deep);levelOrderBFS(res, root.right, deep);
}
- 深度處理：
首先將深度deep加1，因為當前節點的深度比其父節點大1。 - 數組創建與填充：
使用while循環檢查res的大小是否小于deep。如果是，則創建一個新的空列表resList并添加到res中。這確保了res中始終有足夠的子列表來存儲每一層的節點值。
然后，通過res.get(deep - 1).add(root.val)將當前節點的值添加到res中對應深度的子列表中。 - 遞歸調用：
最后，分別對當前節點的左子節點和右子節點進行遞歸調用，深度deep保持不變。這使得遞歸能夠逐層深入，遍歷整個二叉樹。
四、遞歸流程模擬
以二叉樹 [3, 9, 20, null, null, 15, 7] 為例，結構如下：
3/ \9 20/ \15 7
以下是遞歸過程的詳細模擬：
初始狀態
res = []，deep = 0，root = 3
第一次遞歸調用
deep = 1res.size() = 0 < 1，創建新列表[]并添加到res中，此時res = [[]]- 將
3添加到res[0]中，此時res = [[3]] - 對
root.left（即9）進行遞歸調用，deep = 1 - 對
root.right（即20）進行遞歸調用，deep = 1
對 9 的遞歸調用
deep = 2res.size() = 1 < 2，創建新列表[]并添加到res中，此時res = [[3], []]- 將
9添加到res[1]中，此時res = [[3], [9]] - 對
root.left（即null）進行遞歸調用，deep = 2 - 對
root.right（即null）進行遞歸調用，deep = 2
對 20 的遞歸調用
deep = 2res.size() = 2 == 2，直接將20添加到res[1]中，此時res = [[3], [9, 20]]- 對
root.left（即15）進行遞歸調用，deep = 2 - 對
root.right（即7）進行遞歸調用，deep = 2
對 15 的遞歸調用
deep = 3res.size() = 2 < 3，創建新列表[]并添加到res中，此時res = [[3], [9, 20], []]- 將
15添加到res[2]中，此時res = [[3], [9, 20], [15]] - 對
root.left（即null）進行遞歸調用，deep = 3 - 對
root.right（即null）進行遞歸調用，deep = 3
對 7 的遞歸調用
deep = 3res.size() = 3 == 3，直接將7添加到res[2]中，此時res = [[3], [9, 20], [15, 7]]- 對
root.left（即null）進行遞歸調用，deep = 3 - 對
root.right（即null）進行遞歸調用，deep = 3
最終結果
res = [[3], [9, 20], [15, 7]]
五、關鍵知識點總結
1. 遞歸的基本概念
遞歸是一種解決問題的方法，它通過將問題分解為更小的子問題，并通過調用自身來解決這些子問題。在二叉樹的層序遍歷中，我們通過遞歸調用自身來遍歷每一層的節點。
2. 深度優先搜索（DFS）與廣度優先搜索（BFS）
遞歸法本質上是一種深度優先搜索（DFS）的應用。與廣度優先搜索（BFS）不同，DFS會沿著一條路徑一直深入下去，直到無法繼續，然后再回溯到上一層，繼續探索其他路徑。在層序遍歷中，我們通過遞歸實現了一種特殊的DFS，它能夠逐層遍歷二叉樹的節點。
3. 動態數組的使用
在遞歸過程中，我們使用了一個動態數組 res 來存儲每一層的節點值。動態數組的特點是可以根據需要動態地增加或減少元素，這使得我們能夠靈活地處理不同層級的節點數量。
六、完整代碼
import java.util.ArrayList;
import java.util.List;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();levelOrderBFS(res, root, 0);return res;}public void levelOrderBFS(List<List<Integer>> res, TreeNode root, int deep) {if (root == null) {return;}deep++;while (res.size() < deep) {List<Integer> resList = new ArrayList<>();res.add(resList);}res.get(deep - 1).add(root.val);levelOrderBFS(res, root.left, deep);levelOrderBFS(res, root.right, deep);}
}
七、總結
遞歸法解決二叉樹的層序遍歷問題雖然不像隊列法那樣直觀，但它展示了深度優先搜索在樹形結構中的巧妙應用。通過理解臨時數組的創建邏輯和遞歸的具體實現，我們能夠更好地掌握遞歸的思想和技巧。在實際應用中，遞歸法可能在某些情況下比隊列法更簡潔高效，尤其是對于一些復雜的樹形結構或需要深度優先處理的問題。希望本文的講解能夠幫助讀者更好地理解和掌握遞歸法解決二叉樹層序遍歷的核心難點。
