173.二叉树：找树左下角的值（力扣）

代码解决

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr, right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    // 查找二叉树中最底层最左边的值
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;  // 定义一个队列用于广度优先搜索
        if (root != nullptr) que.push(root);  // 如果根节点不为空，将其加入队列
        
        int result;  // 用于保存最终结果，即最底层最左边的节点值
        
        // 当队列不为空时进行循环
        while (!que.empty()) {
            int size = que.size();  // 获取当前队列的大小
            TreeNode* node;  // 用于存储当前节点
            
            // 遍历当前层的所有节点
            for (int i = 0; i < size; i++) {
                node = que.front();  // 取出队列的头节点
                que.pop();  // 弹出头节点
                
                // 如果是当前层的第一个节点，更新结果
                if (i == 0) result = node->val;
                
                // 如果左子节点存在，将其加入队列
                if (node->left) que.push(node->left);
                
                // 如果右子节点存在，将其加入队列
                if (node->right) que.push(node->right);
            }
        }
        
        return result;  // 返回最底层最左边的节点值
    }
};

findBottomLeftValue 方法：

• 使用广度优先搜索（BFS）来遍历二叉树。
• 定义一个队列 que 来存储节点，用于层次遍历。
• 如果根节点不为空，将其加入队列。
• 初始化 result 用于保存最底层最左边的节点值。
• 当队列不为空时，进行循环：
  • 获取当前层的节点数量 size。
  • 遍历当前层的所有节点：
    • 取出队列的头节点 node 并弹出。
    • 如果是当前层的第一个节点，更新 result。
    • 如果左子节点存在，将其加入队列。
    • 如果右子节点存在，将其加入队列。
• 返回 result，即最底层最左边的节点值。

方法二 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr, right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int maxdeep = INT_MIN;  // 用于存储最大的深度
    int result;  // 用于存储最底层最左边的节点值

    // 递归遍历函数，找到最底层最左边的节点
    void traversal(TreeNode* root, int depth) {
        // 如果当前节点是叶子节点
        if (root->left == nullptr && root->right == nullptr) {
            // 更新最大深度和结果
            if (depth > maxdeep) {
                maxdeep = depth;
                result = root->val;
            }
            return;
        }

        // 递归遍历左子树
        if (root->left) {
            traversal(root->left, depth + 1);  // 深度加1
        }

        // 递归遍历右子树
        if (root->right) {
            traversal(root->right, depth + 1);  // 深度加1
        }
    }

    // 主函数，调用递归遍历函数
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);  // 从根节点开始遍历，初始深度为0
        return result;  // 返回最底层最左边的节点值
    }
};

• 成员变量：

  • maxdeep：存储最大深度，初始值为 INT_MIN。
  • result：存储最底层最左边的节点值。

• traversal 方法：

  • 递归遍历二叉树，找到最底层最左边的节点。
  • 如果当前节点是叶子节点，检查当前深度是否大于 maxdeep，如果是，更新 maxdeep 和 result。
  • 递归遍历左子树和右子树，深度加1。

• findBottomLeftValue 方法：

  • 主函数，调用 traversal 方法从根节点开始遍历，初始深度为 0。
  • 返回最底层最左边的节点值 result。