一、題目本質與核心訴求解析

在二叉樹算法問題中，"找樹左下角的值"是一個典型的結合深度與位置判斷的問題。題目要求我們找到二叉樹中最深層最左邊的節點值，這里的"左下角"有兩個關鍵限定：

• 深度優先：必須是深度最大的那一層節點
• 最左優先：在最深層中選擇最左邊的那個節點

先來看一個示例二叉樹：

    1/ \2   3/   / \
4   5   6/7

在這個樹中，最深層是第3層（根節點為第0層時是第2層），該層最左節點是7，因此正確輸出為7。理解這個問題的核心在于如何在遞歸過程中同時追蹤節點深度和左右位置關系，這也是本文要重點解析的內容。

二、遞歸解法的核心實現與數據結構設計

完整遞歸代碼實現

/*** Definition for a binary tree node.* public 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 {private int Deep = -1;  // 記錄當前最大深度private int res = 0;    // 記錄最深層最左節點值public int findBottomLeftValue(TreeNode root) {findLeftVal(root, 0);  // 從根節點開始，深度初始為0return res;}public void findLeftVal(TreeNode root, int deep) {if (root == null) {return;}// 處理葉子節點：判斷是否更新最深層最左節點if (root.left == null && root.right == null) {if (deep > Deep) {res = root.val;Deep = deep;}return;}// 先遞歸左子樹，保證左子樹優先訪問if (root.left != null) {findLeftVal(root.left, deep + 1);}// 再遞歸右子樹if (root.right != null) {findLeftVal(root.right, deep + 1);}}
}

關鍵數據結構設計解析

1. Deep變量：

   • 作用：記錄當前發現的最大深度
   • 初始值：-1（因為根節點深度從0開始，確保第一個葉子節點會更新該值）
   • 更新時機：當遇到更深的葉子節點時更新

2. res變量：

   • 作用：存儲最深層最左節點的值
   • 更新原則：僅當遇到更深的葉子節點，或者同深度但更左的葉子節點時更新（由于先左后右遞歸，同深度下左節點必然先訪問）

3. deep參數：

   • 作用：當前遞歸層的節點深度
   • 傳遞方式：每次遞歸進入子節點時深度+1
   • 意義：明確當前節點在樹中的層級位置

三、核心問題解析：遞歸中如何判斷最深層最左節點

1. 深度優先搜索的順序控制

本算法采用先左后右的深度優先搜索順序，這是確保找到"最左"節點的關鍵：

• 遞歸調用順序：先處理左子樹，再處理右子樹
• 核心邏輯：在同一深度下，左子樹的節點會比右子樹的節點先被訪問
• 效果：當存在多個同深度節點時，左節點會優先被判定為當前最深層最左節點

2. 深度判斷與更新機制

if (root.left == null && root.right == null) {if (deep > Deep) {res = root.val;Deep = deep;}
}

• 葉子節點判斷：當節點左右子樹都為空時，確定為葉子節點
• 深度比較：如果當前葉子節點深度大于已記錄的最大深度Deep，則更新結果
• 更新策略：
  1. 更深的葉子節點：直接更新res和Deep
  2. 同深度的葉子節點：由于先左后右遞歸，左節點先訪問，res不會被右節點覆蓋

3. 遞歸終止與回溯邏輯

• 終止條件：
  1. 遇到空節點時直接返回（遞歸邊界）
  2. 處理完葉子節點后返回（不再繼續遞歸）
• 回溯作用：當左子樹遞歸完成后，回溯到父節點，再進入右子樹遞歸，確保左右子樹都被遍歷

四、遞歸流程深度模擬：以示例二叉樹為例

示例二叉樹結構（根節點深度為0）：

    1(0)/   \2(1)  3(1)/     / \
4(2)  5(2) 6(2)/7(3)

詳細遞歸執行過程

1. 初始狀態：

   • Deep = -1, res = 0
   • 調用findLeftVal(root, 0)，root為節點1，深度0

2. 處理節點1（深度0）：

   • 非葉子節點，進入左子樹調用findLeftVal(2, 1)

3. 處理節點2（深度1）：

   • 非葉子節點，進入左子樹調用findLeftVal(4, 2)

4. 處理節點4（深度2）：

   • 是葉子節點（左右子樹為空）
   • 深度2 > Deep(-1)，更新res=4, Deep=2
   • 返回上一層（節點2）

5. 節點2的右子樹為空，返回上一層（節點1）

6. 節點1進入右子樹調用findLeftVal(3, 1)

7. 處理節點3（深度1）：

   • 非葉子節點，進入左子樹調用findLeftVal(5, 2)

8. 處理節點5（深度2）：

   • 非葉子節點，進入左子樹調用findLeftVal(7, 3)

9. 處理節點7（深度3）：

   • 是葉子節點
   • 深度3 > Deep(2)，更新res=7, Deep=3
   • 返回上一層（節點5）

10. 節點5的右子樹為空，返回上一層（節點3）

11. 節點3進入右子樹調用findLeftVal(6, 2)

12. 處理節點6（深度2）：

    • 是葉子節點
    • 深度2 < Deep(3)，不更新res
    • 返回上一層（節點3）

13. 所有遞歸結束，返回res=7

五、算法復雜度與遞歸特性分析

1. 時間復雜度分析

• O(n)：每個節點僅被訪問一次，n為樹的節點總數
• 原因：遞歸過程中對每個節點進行一次深度判斷，無重復訪問

2. 空間復雜度分析

• O(h)：h為樹的高度，取決于遞歸棧的最大深度
• 最壞情況：樹退化為鏈表時，h=n，空間復雜度O(n)
• 平均情況：平衡二叉樹h=logn，空間復雜度O(logn)

3. 遞歸算法的優勢與局限

優勢	局限
代碼邏輯簡潔，符合樹的遞歸定義	可能因棧溢出無法處理極大樹
天然支持深度優先搜索順序控制	空間復雜度與樹深度相關
先左后右的遞歸順序自然實現"最左"優先	調試相比迭代更困難

六、核心技術點總結：遞歸找最左節點的三大關鍵

1. 深度優先搜索順序控制

• 先左后右的遞歸順序是實現"最左"優先的核心
• 遞歸天然保證左子樹先于右子樹處理，確保同深度下左節點優先被訪問

2. 深度追蹤與比較機制

• 通過參數傳遞當前深度，全局變量記錄最大深度
• 葉子節點處進行深度比較，確保只保留最深層節點

3. 優先更新策略

• 深度更大時：無條件更新結果
• 深度相同時：由于左子樹先處理，結果不會被右節點覆蓋
• 實現了"深度優先，同深度左優先"的判定邏輯

七、拓展思考：遞歸與迭代解法的對比與適用場景

1. 與層序遍歷迭代法的對比

方法	核心思想	時間復雜度	空間復雜度	優勢場景
遞歸	深度優先+先左后右	O(n)	O(h)	代碼簡潔、樹深度較小
迭代	廣度優先+層序處理	O(n)	O(m)（m為最大層寬度）	處理極大樹、避免棧溢出

2. 大廠面試中的策略建議

• 當樹深度較小時，遞歸解法更簡潔高效
• 當樹可能很深時，應考慮迭代解法避免棧溢出
• 面試中可先給出遞歸解法，再主動說明迭代優化方向

八、總結：遞歸解法的核心設計哲學

本遞歸算法通過"深度優先搜索+先左后右順序+深度追蹤"的組合策略，巧妙解決了找樹左下角值的問題。其核心設計哲學包括：

1. 深度優先的天然優勢：遞歸天然適合深度優先搜索，能自然追蹤節點深度
2. 順序控制的重要性：先左后右的遞歸順序是實現"最左"優先的關鍵
3. 狀態傳遞的巧妙設計：通過參數傳遞深度，全局變量記錄結果，實現狀態追蹤
4. 葉子節點的關鍵作用：僅在葉子節點處判斷是否更新結果，提高算法效率

理解這種遞歸設計思路，不僅能解決本題，還能為類似的二叉樹深度與位置相關問題提供通用解法。在實際應用中，可根據樹的規模和場景選擇遞歸或迭代實現，靈活應對不同需求。