一、題目深度解析與核心訴求
在二叉樹的眾多問題中，尋找最深層最左節點的值是一個兼具趣味性與代表性的問題。題目要求我們在給定的二叉樹中，找到深度最大的那一層中最左邊的節點值。如果存在多個最深層，只需返回最左邊節點的值即可。
這個問題的核心難點在于：
- 如何準確判斷樹的最深層
- 如何在最深層中找到最左邊的節點
- 如何高效地實現這一查找過程
為了更好地理解問題，我們來看一個示例：
對于如下二叉樹：
1/ \2 3/ / \
4 5 6/7
最深層是第3層（假設根節點為第1層），該層最左節點是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 {public int findBottomLeftValue(TreeNode root) {int res = 0;Deque<TreeNode> cur = new ArrayDeque<>();TreeNode temp = root;cur.offer(temp);int cnt = 0;while (!cur.isEmpty()) {int len = cur.size();cnt = 0;while (len > 0) {temp = cur.poll();if (cnt == 0) {res = temp.val;}if (temp.left != null) {cur.offer(temp.left);}if (temp.right != null) {cur.offer(temp.right);}cnt++;len--;}}return res;}
}
三、核心問題解析：如何判斷最深層最左節點
1. 層序遍歷與深度判斷
層序遍歷的一個重要特點是按層處理節點，每處理完一層，才會處理下一層。在這個算法中，我們使用一個隊列來實現層序遍歷。每次從隊列中取出當前層的所有節點，處理完后，隊列中剩下的就是下一層的節點。
具體來說：
- 初始時，將根節點加入隊列
- 每次循環處理一層的節點：
- 首先獲取當前隊列的大小，這個大小就是當前層的節點數
- 然后依次取出當前層的所有節點，處理它們的子節點
- 處理完當前層后，隊列中剩下的就是下一層的節點
這種處理方式使得我們可以很方便地按層處理節點，從而能夠準確地判斷當前處理的是哪一層。
2. 最左節點的判斷
在每一層的處理中，我們需要找到最左邊的節點。由于隊列是先進先出（FIFO）的結構，因此每一層中最先取出的節點就是該層最左邊的節點。
具體實現中，我們使用一個計數器cnt來記錄當前取出的是當前層的第幾個節點。當cnt=0時，說明取出的是當前層的第一個節點，也就是最左邊的節點，此時將該節點的值賦給結果變量res。
3. 最深層的確定
由于層序遍歷是按層處理的，因此最后處理的一層就是最深層。在處理最深層時，我們取出的第一個節點就是最深層最左的節點，其值會被賦給res，最終返回這個值。
四、算法流程模擬與詳細解釋
以之前的示例二叉樹為例，我們來模擬一下算法的執行過程：
二叉樹結構：
1/ \2 3/ / \
4 5 6/7
-
初始狀態：
- 隊列中有節點1
res=0cnt=0
-
第一次循環（處理第1層）：
len=1（當前層節點數）- 進入內層循環，
len>0：- 取出節點1，
cnt=0，res=1 - 將節點1的左子節點2和右子節點3加入隊列
cnt=1，len=0
- 取出節點1，
- 內層循環結束，隊列中有節點2、3
-
第二次循環（處理第2層）：
len=2（當前層節點數）- 進入內層循環，
len>0：- 取出節點2，
cnt=0，res=2 - 將節點2的左子節點4加入隊列（右子節點為空）
cnt=1，len=1- 取出節點3，
cnt=1，不更新res - 將節點3的左子節點5和右子節點6加入隊列
cnt=2，len=0
- 取出節點2，
- 內層循環結束，隊列中有節點4、5、6
-
第三次循環（處理第3層）：
len=3（當前層節點數）- 進入內層循環，
len>0：- 取出節點4，
cnt=0，res=4 - 節點4的左右子節點均為空，不加入隊列
cnt=1，len=2- 取出節點5，
cnt=1，不更新res - 將節點5的左子節點7加入隊列（右子節點為空）
cnt=2，len=1- 取出節點6，
cnt=2，不更新res - 節點6的左右子節點均為空，不加入隊列
cnt=3，len=0
- 取出節點4，
- 內層循環結束，隊列中有節點7
-
第四次循環（處理第4層）：
len=1（當前層節點數）- 進入內層循環，
len>0：- 取出節點7，
cnt=0，res=7 - 節點7的左右子節點均為空，不加入隊列
cnt=1，len=0
- 取出節點7，
- 內層循環結束，隊列為空
-
循環結束，返回
res=7，即最深層最左節點的值。
五、算法復雜度分析
- 時間復雜度：O(n)，其中n是樹的節點數。因為我們需要訪問每個節點一次。
- 空間復雜度：O(m)，其中m是樹的最大寬度。在層序遍歷中，隊列的大小最多為樹的最大寬度，也就是同一層的節點數。
六、算法的核心優勢與適用場景
1. 優勢
- 層序遍歷的方式使得我們可以很方便地按層處理節點，準確判斷最深層
- 利用隊列的FIFO特性，輕松找到每一層的最左節點
- 算法邏輯清晰，實現簡單，時間復雜度和空間復雜度都比較理想
2. 適用場景
- 當需要按層處理二叉樹節點時
- 當問題涉及到樹的深度或某一層的節點時
- 當需要找到某一層的特定位置節點時
七、總結：層序遍歷的深度與順序控制
在尋找樹的左下角值的問題中，我們利用層序遍歷的特性，巧妙地解決了深度判斷和最左節點查找的問題。這種方法的核心在于：
- 利用隊列實現層序遍歷，按層處理節點
- 通過記錄每一層的節點數，準確判斷當前處理的是哪一層
- 利用隊列的FIFO特性，第一個取出的節點即為當前層的最左節點
- 由于層序遍歷是按層進行的，最后處理的一層就是最深層，該層的最左節點即為所求
這種方法不僅解決了當前的問題，也為解決其他類似的二叉樹問題提供了思路。例如，尋找最深層最右節點、計算某一層的節點和等問題，都可以基于層序遍歷的思想來解決。
通過這個問題，我們可以看到，合理利用數據結構的特性（如隊列的FIFO特性），并結合問題的特點（按層處理），可以設計出高效、簡潔的算法。這也是解決算法問題的關鍵所在。
)
