找树左下角的值
# 📃 题目描述
题目链接:
- 剑指 Offer II 045. 二叉树最底层最左边的值 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 513. 找树左下角的值 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
# 🔔 解题思路
注意,这里是最底层最左边的节点,没有特别说明一定得是左孩子,所以这题就变得很简单了,直接层序遍历,最后一层的第一个节点就是题目要的结果
那么,如何找到最后一层的第一个节点呢?
我们使用一个变量记录 res 每层的第一个节点即可,每遍历一层,这个变量就会被重新赋值一次。这样,整颗树遍历结束后,这个变量 res 就指向最后一层的第一个节点
class Solution {
public int findBottomLeftValue(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return root.val;
}
Queue<TreeNode> queue = new LinkedList<>();
// 根节点入队
queue.offer(root);
// 记录每层的第一个节点
int res = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i ++) {
TreeNode cur = queue.poll();
if (i == 0) {
res = cur.val;
}
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:O(LogN)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10