LeetCode 题解工作台
找树左下角的值
给定一个二叉树的 根节点 root ，请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root = [2,1,3] 输出: 1 示例 2: 输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7 提示: 二叉树的节点个数的范围…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
BFS 找最后一层第一个节点。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
提示:
- 二叉树的节点个数的范围是
[1,104] -231 <= Node.val <= 231 - 1
解题思路
方法一：BFS
BFS 找最后一层第一个节点。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
q = deque([root])
ans = 0
while q:
ans = q[0].val
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Tests the candidate's understanding of binary tree traversal techniques.
- question_mark
Evaluates their ability to track state across recursive or iterative calls.
- question_mark
Assesses how well they handle edge cases like trees with only one node or very unbalanced trees.
常见陷阱
外企场景- error
Forgetting to track the leftmost value at the deepest level, leading to an incorrect answer.
- error
Failing to handle edge cases such as when the tree only contains one node or is unbalanced.
- error
Using an inefficient traversal strategy that doesn't take advantage of level-order exploration.
进阶变体
外企场景- arrow_right_alt
Consider the scenario where you need to find the rightmost value of the last row instead of the leftmost.
- arrow_right_alt
What if the tree is a sparse binary tree with large depth?
- arrow_right_alt
How would the solution change if the task was to return the bottom-most value for any given row, not just the last row?