0513. Find Bottom Left Tree Value

题目信息

题号:

0513

难度:

Medium

主题:

二叉树、最深层、最左节点、层级顺序

原题:

LeetCode 0513

重点:

返回最大深度那一层最先出现的节点值、不是几何坐标最小值、根节点非空

题目重述

给定一棵非空二叉树,找到树中最深一层的最左侧节点,并返回该节点的值。这里的“最左侧”按二叉树从左到右的层级顺序判断,而不是比较节点值大小。

若最深层只有一个节点,直接返回该节点值;若整棵树只有根节点,根节点同时也是最深层最左节点。

自建示例

最深节点位于左侧分支:

输入:root = [8,4,10,2,6,null,12,1]
输出:1
解释:最深层只有节点 1,因此它也是该层最左侧节点。

只有根节点:

输入:root = [5]
输出:5
解释:根节点是唯一节点,也是最深层的最左节点。

层序遍历中每层第一个节点

队列按从左到右保存当前层。每轮开始时队首就是这一层最左节点,将它记录为 answer,再处理整层并把孩子按左右顺序加入队尾。遍历结束时最后一次更新对应最深层的最左节点。

C++ 实现

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        std::queue<TreeNode*> queue;
        queue.push(root);
        int answer = root->val;
        while (!queue.empty()) {
            int levelSize = static_cast<int>(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 是最大层宽。