leetcode题解513：找树左下角的值（递归中的回溯处理）！

一、题目内容：

题目要求找到一个二叉树的最底层最左边节点的值。具体来说，我们需要从根节点开始遍历二叉

树，找到最深的那层中的最左边的节点，并返回该节点的值。因为要先找到最底层左侧的值，所以我们选择遍历顺序一定是左侧先遍历，右侧后遍历。

我们需要声明depth、MaxDepth和result，depth记录当前深度、MaxDepth记录最大深度深度、result记录深度最大值，但在遍历中我么会思考到，如果遍历到某一叶子节点，但是当前结点深度并不是最大的，那么递归会回退到其父结点，这时就需要将深度回溯，这一过程如何实现呢，我们会在代码中体现。

二、题目分析

输入和输出

输入：二叉树的根节点 root。
- 二叉树的每个节点是一个 TreeNode 对象，包含：
  - val：节点的值（整数）。
  - left：指向左子节点的指针。
  - right：指向右子节点的指针。
输出：最底层最左边节点的值（整数）。

深度优先遍历函数 `trevesal`：

参数：
- root：当前节点。
- depth：当前节点的深度。
逻辑：
- 如果当前节点是叶子节点（即没有左子节点和右子节点）则：
  - 如果当前深度 depth 大于 maxDepth，则更新 maxDepth 和 result。
- 如果当前节点有左子节点则：
  - 递归调用 trevesal，深度加1。
- 如果当前节点有右子节点则：
  - 递归调用 trevesal，深度加1。
- 回溯：在递归调用结束后，深度减1，以恢复到当前节点的深度。

三、代码解答

1.C++代码

class Solution {
public:int maxDepth = INT_MIN;  // 用于记录当前找到的最深的叶子节点的深度int result;              // 用于存储最底层最左边节点的值// 定义递归函数，用于深度优先搜索void trevesal(TreeNode *root, int depth) {// 如果当前节点是叶子节点（没有左子节点和右子节点）if (root->left == NULL && root->right == NULL) {// 如果当前深度大于已知的最大深度if (depth > maxDepth) {result = root->val;  // 更新结果值为当前节点的值maxDepth = depth;    // 更新最大深度为当前深度}}// 如果当前节点有左子节点if (root->left) {depth++;  // 深度加1，进入下一层trevesal(root->left, depth);  // 递归遍历左子节点depth--;  // 回溯，恢复到当前节点的深度}// 如果当前节点有右子节点if (root->right) {depth++;  // 深度加1，进入下一层trevesal(root->right, depth);  // 递归遍历右子节点depth--;  // 回溯，恢复到当前节点的深度}}// 主函数，用于调用递归函数并返回结果int findBottomLeftValue(TreeNode* root) {trevesal(root, 0);  // 从根节点开始，深度为0return result;      // 返回最底层最左边节点的值}
};

详细注释

1. 成员变量

int maxDepth = INT_MIN;  // 初始化为最小整数，表示当前找到的最深的叶子节点的深度
int result;              // 用于存储最底层最左边节点的值

maxDepth：记录当前找到的最深的叶子节点的深度，初始值为 INT_MIN，确保任何叶子节点的深度都会比它大。
result：存储最底层最左边节点的值，初始值未定义，会在递归过程中被赋值。

2. 递归函数 `trevesal`

void trevesal(TreeNode *root, int depth) {// 如果当前节点是叶子节点（没有左子节点和右子节点）if (root->left == NULL && root->right == NULL) {// 如果当前深度大于已知的最大深度if (depth > maxDepth) {result = root->val;  // 更新结果值为当前节点的值maxDepth = depth;    // 更新最大深度为当前深度}}// 如果当前节点有左子节点if (root->left) {depth++;  // 深度加1，进入下一层trevesal(root->left, depth);  // 递归遍历左子节点depth--;  // 回溯，恢复到当前节点的深度}// 如果当前节点有右子节点if (root->right) {depth++;  // 深度加1，进入下一层trevesal(root->right, depth);  // 递归遍历右子节点depth--;  // 回溯，恢复到当前节点的深度}
}

叶子节点检查：
- 如果当前节点没有左子节点和右子节点，说明它是一个叶子节点。
- 如果当前叶子节点的深度大于已知的最大深度 maxDepth，则更新 result 和 maxDepth。
递归遍历左子节点：
- 如果当前节点有左子节点，深度加1，递归调用 trevesal 遍历左子节点。
- 递归返回后，深度减1，恢复到当前节点的深度。这是回溯的关键步骤，确保每次递归返回后，深度值正确。
递归遍历右子节点：
- 如果当前节点有右子节点，深度加1，递归调用 trevesal 遍历右子节点。
- 递归返回后，深度减1，恢复到当前节点的深度。同样，这是回溯的关键步骤。

3. 主函数 `findBottomLeftValue`

int findBottomLeftValue(TreeNode* root) {trevesal(root, 0);  // 从根节点开始，深度为0return result;      // 返回最底层最左边节点的值
}

调用递归函数：
- 从根节点开始，初始深度为0，调用 trevesal 函数。
返回结果：
- 递归完成后，返回 result，即最底层最左边节点的值。

回溯和递归的详细解释

递归

递归是一种函数调用自身的方法，用于解决复杂问题。在本题中，递归用于遍历二叉树的每个节点。
每次递归调用时，深度 depth 增加1，表示进入下一层。
递归调用的终止条件是当前节点是叶子节点（没有左子节点和右子节点）。

回溯

回溯是一种在递归调用返回后恢复状态的机制。
在本题中，每次递归调用返回后，深度 depth 减1，恢复到当前节点的深度。
这样可以确保每次递归返回后，深度值正确，不会影响后续的递归调用。

示例

假设二叉树如下：

    1/ \2   3/   / \
4   5   6

遍历过程

从根节点 1 开始，深度为0。
- 调用 trevesal(1, 0)。
遍历左子节点 2，深度为1。
- 调用 trevesal(2, 1)。
遍历左子节点 4，深度为2。
- 调用 trevesal(4, 2)。
- 4 是叶子节点，且深度大于 maxDepth，更新 maxDepth=2 和 result=4。
- 返回到节点 2，深度减1，恢复为1。
返回到根节点 1，深度减1，恢复为0。
遍历右子节点 3，深度为1。
- 调用 trevesal(3, 1)。
遍历左子节点 5，深度为2。
- 调用 trevesal(5, 2)。
- 5 是叶子节点，但深度等于 maxDepth，不更新。
- 返回到节点 3，深度减1，恢复为1。
遍历右子节点 6，深度为2。
- 调用 trevesal(6, 2)。
- 6 是叶子节点，但深度等于 maxDepth，不更新。
- 返回到节点 3，深度减1，恢复为1。
返回到根节点 1，深度减1，恢复为0。