【513. 找树左下角的值 中等】

题目：

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

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

示例 2:

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

提示:

• 二叉树的节点个数的范围是 [1,104]
• -231 <= Node.val <= 231 - 1

---

思路：

1. 递归法

   该题有一个容易迷惑的地方，就是最底层最左边的值并不一定是左叶子节点的值，比如输入：[1,null,1]，那最底层最左边的值就是右叶子节点的值：1。

   所以递归的终止条件不能模仿 404. 左叶子之和中那样写，即不能写成下面这样：

   if(node->left && !node->left->left && !node->left->right){    //  到达左叶子节点，将值累加到resultresult = node->left->val;
   }
   

   这样会漏掉左叶子节点为空，而右叶子节点有值的情况。

   所以应该借助深度来写递归，即记录让深度值变大的第一个值，不论是左叶子节点，还是右叶子节点。最后一次记录的一定是最底层最左边的值。

   递归三部曲：

• 确定递归函数的参数和返回值

  参数必须有要遍历的树的根节点，还有就是一个int型的变量用来记录最长深度。 这里就不需要返回值了，所以递归函数的返回类型为void。

  本题还需要类里的两个全局变量，maxLen用来记录最大深度，result记录最大深度最左节点的数值。

  代码如下：

  int maxDepth = INT_MIN;   // 全局变量 记录最大深度
  int result;       // 全局变量 最大深度最左节点的数值
  void traversal(TreeNode* root, int depth)
  

• 确定终止条件

  当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。

  代码如下：

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

• 确定单层递归的逻辑

  在找最大深度的时候，递归的过程中依然要使用回溯，代码如下：

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

2. 迭代法

   本题使用层序遍历再合适不过了，比递归要好理解得多！

   只需要记录最后一行第一个节点的数值就可以了。

---

代码：

1. 递归法

class Solution {
public:int maxDepth = INT_MIN; // 全局变量 记录最大深度int result; // 全局变量 最大深度最左节点的数值void traversal(TreeNode* root, int depth) {if (root->left == NULL && root->right == NULL) {if (depth > maxDepth) {maxDepth = depth;    // 更新最大深度result = root->val; // 最大深度最左面的数值}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;  //  到达左叶子节点就替换result的值，最后一次就是最底层，最左边节点的值if(node->left) que1.push(node->left);if(node->right) que1.push(node->right);}}return result;}
};

---

总结：

本题比较迷惑的点就是容易误认为最左边的值就是左叶子节点的值，而写错递归的终止条件。

递归法要注意回溯。

---

参考：

代码随想录