LeetCode 补充题 196. 二叉树左视图
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 199. 二叉树的右视图
LeetCode 原题返回右视图；本文改为返回左视图，每层选取最左侧节点。
:::
给定二叉树根节点
root，返回从左侧观察时，每一层最左边的节点值；按从上到下的顺序输出。
示例 1：
输入：
root = [1,2,3]
输出：[1,2]
提示：
- 树可以为空。
- 节点值为
32位整数。
题意分析
左视图取的是每层实际存在的最左节点，并不等于不断沿根的左指针向下走。当左侧分支提前结束时，右侧子树中的更深节点仍可能出现在左视图中。
解法：层序遍历
核心思路
[!blue]
用队列逐层处理。每层开始先固定当前队列长度，这些节点恰好构成本层；处理中加入的孩子属于下一层，不能参与本轮计数。
父节点从左到右出队，每个父节点又先加入左孩子、再加入右孩子，因此下一层仍从左到右排列。本层第一个出队节点就是该层最左节点，只收集这一项即可。空树直接返回空结果。
解题步骤
- 空树返回空列表，否则将根节点入队。
- 每层开始记录队列长度，按这个固定数量依次出队。
- 保存本层第一个节点的值，再按左、右顺序加入每个节点的孩子。
- 队列为空时返回从上到下收集的结果。
代码实现
class Solution {
public List<Integer> leftSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (i == 0) {
res.add(node.val);
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return res;
}
}
func leftSideView(root *TreeNode) []int {
res := make([]int, 0)
if root == nil {
return res
}
queue := []*TreeNode{
root,
}
for len(queue) > 0 {
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
if i == 0 {
res = append(res, node.Val)
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点入队和出队各一次。
- 空间复杂度：辅助队列 $O(w)$，其中 $w$ 为最大层宽；结果占用 $O(h)$，其中 $h$ 为树高。
关键点总结
[!green]
按层遍历，每层先保存节点数，按从左到右的顺序出队，仅收集该层第一个节点。
易错点总结
[!yellow]
- 每层长度在处理前固定，不能随着孩子入队不断延长本轮循环。
- 孩子必须先左后右入队，才能把本层第一个节点作为左视图。
- 不要把左视图简化成根到最左叶子的路径。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 199. 二叉树的右视图 | 中等 | 都按层选取一个可见节点；该题取每层最右节点，本题取最左节点，可调整遍历顺序或每层取值位置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！