1.题目描述
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
2.解题思路与代码
2.1 解题思路
这道题要获取最左侧的节点值，其实就是在获取最后一层最左边第一个节点，因此考虑使用二叉树层序遍历解答。这里就需要使用到层序遍历的一个特点：放入队列的次数等于队列长度时，那么下一层已全部放入队列中。利用这一特性当放入次数等于队列长度时，此时从队列获取队头即是这一层的第一个节点，遍历完成之后便能得到最后一层第一个节点。这里使用数组来模拟一个队列。
2.2 代码
class Solution {
public int findBottomLeftValue(TreeNode root) {
int head = 0;
int tail = 0;
// 使用数组模拟队列
TreeNode[] queue = new TreeNode[10000];
queue[tail++] = root;
int count = 1;
TreeNode ans = null;
while (tail - head > 0) {
if (count == tail - head) {
// 如果入队数等于队列中元素个数，则 ans 等于对头元素，并且计数清零
ans = queue[head];
count = 0;
}
// 弹出队头元素
TreeNode poll = queue[head++];
if (poll.left != null) {
queue[tail++] = poll.left;
count++;
}
if (poll.right != null) {
queue[tail++] = poll.right;
count++;
}
}
return ans.val;
}
}
2.3 测试结果
通过测试
测试结果
3.总结
- 使用二叉树层序遍历，获取每一层第一个节点
- 遍历完成之后便能得到最后一层最左边的节点
- 这里使用数组模拟队列只是单纯的想练习一下队列，也可以用 LinkedList 来操作
