LeetCode513. 找树左下角的值

题目描述

本题目来自LeetCode上的『513. 找树左下角的值』

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层最左边 节点的值。

假设二叉树中至少有一个节点。

示例1：

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示

二叉树的节点个数的范围是 [1,104]
-2^31 <= Node.val <= 2^31 - 1

题解1 - 深度优先搜索

在递归的过程中同时记录树的最大深度，若当前深度大于已知的最大深度则更新答案，我们先遍历左结点再遍历右结点，这样可以保证答案总是最左的结点。

代码

class Solution {
private:
    int maxDepth, ans;
    void dfs(TreeNode* root, int depth, int val) {
        if (root == nullptr) {
            if (depth > maxDepth) {
                ans = val;
                maxDepth = depth;
            }
            return;
        }
        dfs(root->left, depth + 1, root->val);
        dfs(root->right, depth + 1, root->val);
    }
public:
    int findBottomLeftValue(TreeNode* root) {
        dfs(root, 0, root->val);
        return ans;
    }
};

复杂度分析

时间复杂度：$O(n)$
空间复杂度：考虑递归栈为 $O(n)$

题解2 - 广度优先搜索

先让右结点入队，再让左节点入队，这样可以保证队列的最后一个元素是最左结点，当搜索结束后，队列的最后一个元素就是最底层最左结点。

代码

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int ans = 0;
        queue<TreeNode*> q;
        q.emplace(root);
        while (!q.empty()) {
            TreeNode* p = q.front();
            q.pop();
            if (p->right) {
                q.emplace(p->right);
            }
            if (p->left) {
                q.emplace(p->left);
            }
            ans = p->val;
        }
        return ans;
    }
};