題目：

給定一個(gè)二叉樹(shù)的 根節(jié)點(diǎn) root，請(qǐng)找出該二叉樹(shù)的 最底層 最左邊 節(jié)點(diǎn)的值。

假設(shè)二叉樹(shù)中至少有一個(gè)節(jié)點(diǎn)。

示例 1:

輸入: root = [2,1,3]
輸出: 1

示例 2:

輸入: [1,2,3,4,null,5,6,null,null,7]
輸出: 7

提示:

• 二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)的范圍是 [1,104]
• -231 <= Node.val <= 231 - 1

---

思路：

1. 遞歸法

   該題有一個(gè)容易迷惑的地方，就是最底層最左邊的值并不一定是左葉子節(jié)點(diǎn)的值，比如輸入：[1,null,1]，那最底層最左邊的值就是右葉子節(jié)點(diǎn)的值：1。

   所以遞歸的終止條件不能模仿 404. 左葉子之和中那樣寫(xiě)，即不能寫(xiě)成下面這樣：

   if(node->left && !node->left->left && !node->left->right){    //  到達(dá)左葉子節(jié)點(diǎn)，將值累加到resultresult = node->left->val;
   }
   

   這樣會(huì)漏掉左葉子節(jié)點(diǎn)為空，而右葉子節(jié)點(diǎn)有值的情況。

   所以應(yīng)該借助深度來(lái)寫(xiě)遞歸，即記錄讓深度值變大的第一個(gè)值，不論是左葉子節(jié)點(diǎn)，還是右葉子節(jié)點(diǎn)。最后一次記錄的一定是最底層最左邊的值。

   遞歸三部曲：

• 確定遞歸函數(shù)的參數(shù)和返回值

  參數(shù)必須有要遍歷的樹(shù)的根節(jié)點(diǎn)，還有就是一個(gè)int型的變量用來(lái)記錄最長(zhǎng)深度。 這里就不需要返回值了，所以遞歸函數(shù)的返回類(lèi)型為void。

  本題還需要類(lèi)里的兩個(gè)全局變量，maxLen用來(lái)記錄最大深度，result記錄最大深度最左節(jié)點(diǎn)的數(shù)值。

  代碼如下：

  int maxDepth = INT_MIN;   // 全局變量 記錄最大深度
  int result;       // 全局變量 最大深度最左節(jié)點(diǎn)的數(shù)值
  void traversal(TreeNode* root, int depth)
  

• 確定終止條件

  當(dāng)遇到葉子節(jié)點(diǎn)的時(shí)候，就需要統(tǒng)計(jì)一下最大的深度了，所以需要遇到葉子節(jié)點(diǎn)來(lái)更新最大深度。

  代碼如下：

  if (root->left == NULL && root->right == NULL) {
  if (depth > maxDepth) {maxDepth = depth;           // 更新最大深度result = root->val;   // 最大深度最左面的數(shù)值
  }
  return;
  }
  

• 確定單層遞歸的邏輯

  在找最大深度的時(shí)候，遞歸的過(guò)程中依然要使用回溯，代碼如下：

  	                // 中
  if (root->left) {   // 左depth++; // 深度加一traversal(root->left, depth);depth--; // 回溯，深度減一
  }
  if (root->right) { // 右depth++; // 深度加一traversal(root->right, depth);depth--; // 回溯，深度減一
  }
  return;
  

2. 迭代法

   本題使用層序遍歷再合適不過(guò)了，比遞歸要好理解得多！

   只需要記錄最后一行第一個(gè)節(jié)點(diǎn)的數(shù)值就可以了。

---

代碼：

1. 遞歸法

class Solution {
public:int maxDepth = INT_MIN; // 全局變量 記錄最大深度int result; // 全局變量 最大深度最左節(jié)點(diǎn)的數(shù)值void traversal(TreeNode* root, int depth) {if (root->left == NULL && root->right == NULL) {if (depth > maxDepth) {maxDepth = depth;    // 更新最大深度result = root->val; // 最大深度最左面的數(shù)值}return;}if (root->left) {depth++;traversal(root->left, depth);depth--; // 回溯}if (root->right) {depth++;traversal(root->right, depth);depth--; // 回溯}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};

2. 迭代法

class Solution {
public:int findBottomLeftValue(TreeNode* root) {//  if(root == NULL) return 0;int result = 0;queue<TreeNode*> que1;if(root != NULL) que1.push(root);while(!que1.empty()){int size = que1.size();for(int i = 0; i < size; i++){TreeNode* node = que1.front();que1.pop();if(i == 0) result = node->val;  //  到達(dá)左葉子節(jié)點(diǎn)就替換result的值，最后一次就是最底層，最左邊節(jié)點(diǎn)的值if(node->left) que1.push(node->left);if(node->right) que1.push(node->right);}}return result;}
};

---

總結(jié)：

本題比較迷惑的點(diǎn)就是容易誤認(rèn)為最左邊的值就是左葉子節(jié)點(diǎn)的值，而寫(xiě)錯(cuò)遞歸的終止條件。

遞歸法要注意回溯。

---

參考：

代碼隨想錄