C++算法练习-day36——513.找树左下角的值

题目来源：. - 力扣（LeetCode）

题目思路分析

题目要求在一个二叉树中找到最底层最左边的节点的值。最底层指的是树的深度最深的一层，而最左边的节点则是该层中最左侧的节点。为了解决这个问题，我们可以使用广度优先搜索（BFS）策略，因为BFS按层次遍历树，这样我们可以确保在处理每一层节点时，总是先处理完上一层的所有节点。在遍历过程中，记录当前层的第一个节点的值，并在遍历完一层时更新该值，直到遍历完所有层，此时记录的值即为最底层最左边的节点的值。

代码:

#include <queue>  
  
// 二叉树节点的定义  
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:  
    // 使用BFS寻找最底层最左边的节点的值  
    int findBottomLeftValue(TreeNode* root) {  
        // 使用队列来进行广度优先搜索  
        std::queue<TreeNode*> ans;  
        // 初始化队列，将根节点入队  
        ans.push(root);  
        // 初始化val为根节点的值，因为开始时我们默认根节点为最底层最左边的节点  
        int val = root->val;  
          
        // 当队列不为空时，继续遍历  
        while(!ans.empty()){  
            // 获取队列的第一个节点（当前层的第一个节点）  
            TreeNode* pos = ans.front();  
            ans.pop();  
              
            // 更新val为当前节点的值（因为在遍历每一层的第一个节点时会更新val）  
            // 注意：这里只是临时更新，真正的更新发生在遍历完一层之后  
            if(pos->right){  
                // 如果存在右子节点，将其加入队列  
                ans.push(pos->right);  
                // 注意：这里不直接更新val，因为还要检查左子节点  
                // 但由于BFS的特性，左子节点会先于右子节点被处理  
                // 所以，如果左子节点存在，它会覆盖这里的值  
            }  
            if(pos->left){  
                // 如果存在左子节点，将其加入队列  
                ans.push(pos->left);  
                // 更新val为左子节点的值（左子节点会被先处理，因此是有效的更新）  
                val = pos->left->val;  
            }  
            // 注意：这里不需要else，因为右子节点的值可能在左子节点之后被覆盖  
            // 但最终，val会保留为当前层最左边的节点的值  
        }  
        // 遍历完成后，val即为最底层最左边的节点的值  
        return val;  
    }  
};

知识点摘要

1. 广度优先搜索（BFS）：一种图搜索算法，用于遍历或搜索图形数据结构中的节点。BFS从根节点开始，首先访问所有相邻的节点，然后对于每个已访问的节点，再访问它们的所有未访问过的相邻节点，以此类推，直到访问完所有节点。

2. 队列（Queue）：一种先进先出（FIFO）的数据结构，常用于BFS中存储待访问的节点。

3. 二叉树：一种树形数据结构，其中每个节点最多有两个子节点，称为左子节点和右子节点。

通过上述分析，我们了解了如何使用广度优先搜索（BFS）和二叉树的层次遍历来找到最底层最左边的节点的值。BFS通过队列保证了节点按层次顺序被访问，而层次遍历的特性使得我们能够自然地记录每一层的最左边的节点。虽然代码中有一些细节需要注意（如左子节点和右子节点的处理顺序），但整体上，这种方法是直观且有效的。希望这篇文章能帮助你更好地理解和解决类似的问题。