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; }
};知识点摘要
-
广度优先搜索（BFS）：一种图搜索算法，用于遍历或搜索图形数据结构中的节点。BFS从根节点开始，首先访问所有相邻的节点，然后对于每个已访问的节点，再访问它们的所有未访问过的相邻节点，以此类推，直到访问完所有节点。
-
队列（Queue）：一种先进先出（FIFO）的数据结构，常用于BFS中存储待访问的节点。
-
二叉树：一种树形数据结构，其中每个节点最多有两个子节点，称为左子节点和右子节点。
通过上述分析，我们了解了如何使用广度优先搜索（BFS）和二叉树的层次遍历来找到最底层最左边的节点的值。BFS通过队列保证了节点按层次顺序被访问，而层次遍历的特性使得我们能够自然地记录每一层的最左边的节点。虽然代码中有一些细节需要注意（如左子节点和右子节点的处理顺序），但整体上，这种方法是直观且有效的。希望这篇文章能帮助你更好地理解和解决类似的问题。