题目描述
这是 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 == null) return ;
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 原题链接和其他优选题解。
本文由mdnice多平台发布
