宫水三叶的刷题日记

V1

2022/06/22阅读:14主题:前端之巅同款

【高频笔试题】513. 找树左下角的值

题目描述

这是 LeetCode 上的 513. 找树左下角的值 ,难度为 中等

Tag : 「BFS」、「DFS」、「树的遍历」

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

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

示例 1:

输入: root = [2,1,3]

输出: 1

示例 2:

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

输出: 7

提示:

  • 二叉树的节点个数的范围是

BFS

使用 BFS 进行「层序遍历」,每次用当前层的首个节点来更新 ans,当 BFS 结束后,ans 存储的是最后一层最靠左的节点。

代码:

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        int ans = 0;
        while (!d.isEmpty()) {
            int sz = d.size();
            ans = d.peek().val;
            while (sz-- > 0) {
                TreeNode poll = d.pollFirst();
                if (poll.left != null) d.addLast(poll.left);
                if (poll.right != null) d.addLast(poll.right);
            }
        }
        return ans;
    }
}
  • 时间复杂度:
  • 空间复杂度:最坏情况下所有节点都在同一层,复杂度为

DFS

同理,可以使用 DFS 进行树的遍历,每次优先 DFS 当前节点的左子树,每次第一次搜索到当前深度 depth 时,必然是当前深度的最左节点,此时用当前节点值来更新 ans

代码:

class Solution {
    int max, ans;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 1);
        return ans;
    }
    void dfs(TreeNode root, int depth) {
        if (root == nullreturn ;
        if (depth > max) {
            max = depth; ans = root.val;
        }
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }
}
  • 时间复杂度:
  • 空间复杂度:最坏情况下退化成链,递归深度为 。复杂度为

最后

这是我们「刷穿 LeetCode」系列文章的第 No.513 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

分类:

后端

标签:

数据结构与算法

作者介绍

宫水三叶的刷题日记
V1