0513. Find Bottom Left Tree Value ================================ 题目信息 -------- :题号: 0513 :难度: Medium :主题: 二叉树、最深层、最左节点、层级顺序 :原题: `LeetCode 0513 `_ :重点: 返回最大深度那一层最先出现的节点值、不是几何坐标最小值、根节点非空 题目重述 -------- 给定一棵非空二叉树,找到树中最深一层的最左侧节点,并返回该节点的值。这里的“最左侧”按二叉树从左到右的层级顺序判断,而不是比较节点值大小。 若最深层只有一个节点,直接返回该节点值;若整棵树只有根节点,根节点同时也是最深层最左节点。 自建示例 -------- 最深节点位于左侧分支: .. code-block:: text 输入:root = [8,4,10,2,6,null,12,1] 输出:1 解释:最深层只有节点 1,因此它也是该层最左侧节点。 只有根节点: .. code-block:: text 输入:root = [5] 输出:5 解释:根节点是唯一节点,也是最深层的最左节点。 层序遍历中每层第一个节点 ------------------------ 队列按从左到右保存当前层。每轮开始时队首就是这一层最左节点,将它记录为 ``answer``,再处理整层并把孩子按左右顺序加入队尾。遍历结束时最后一次更新对应最深层的最左节点。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int findBottomLeftValue(TreeNode* root) { std::queue queue; queue.push(root); int answer = root->val; while (!queue.empty()) { int levelSize = static_cast(queue.size()); answer = queue.front()->val; for (int i = 0; i < levelSize; ++i) { TreeNode* node = queue.front(); queue.pop(); if (node->left != nullptr) queue.push(node->left); if (node->right != nullptr) queue.push(node->right); } } return answer; } }; 代码分析 -------- 每层先读取队首再处理孩子,保证记录的是该层最左而非最后访问节点;队列层序顺序使最后一层自然是最深层。每个节点入队出队一次,时间复杂度为 ``O(n)``,队列空间为 ``O(w)``,其中 ``w`` 是最大层宽。