LeetCode 513.找树左下角的值

2024-05-11 02:20
文章标签 leetcode 左下角 513 找树

本文主要是介绍LeetCode 513.找树左下角的值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode 513.找树左下角的值

1、题目

题目链接：513. 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

示例 1:
image.png

输入: root = [2,1,3]
输出: 1

示例 2:
image.png

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

  • 二叉树的节点个数的范围是 [1,104]
  • -231 <= Node.val <= 231 - 1

2、深度优先搜索（递归）

思路

这道题要在二叉树的 最后一行 找到 最左边的值。
如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行。所以要找深度最大的叶子节点。
那么如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。
我们使用 maxDepth 用来记录最大深度，result 记录最大深度最左节点的数值。
在写递归时，我们要先明确递归三部曲：

  1. 确定递归函数的参数和返回值

参数必须有要遍历的树的根节点，depth 用来记录当前深度，maxDepth 用来记录最大深度，result 记录最大深度最左节点的数值。 这里就不需要返回值了，所以递归函数的返回类型为 void。
代码如下：

void traversal(TreeNode* root, int depth, int& maxDepth, int& result)
  1. 确定终止条件

当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度。
代码如下：

// 如果当前节点是叶子节点
if (root->left == nullptr && root->right == nullptr) {// 如果当前深度大于最大深度if (depth > maxDepth) {// 更新最大深度maxDepth = depth;// 更新结果值为当前节点的值result = root->val;}return;
}
  1. 确定单层递归的逻辑

在找最大深度的时候，递归的过程中依然要使用回溯。
代码如下：

// 如果左子节点存在
if (root->left) {// 深度加1depth++;// 递归遍历左子树traversal(root->left, depth, maxDepth, result);// 回溯，深度减1depth--;
}
// 如果右子节点存在
if (root->right) {// 深度加1depth++;// 递归遍历右子树traversal(root->right, depth, maxDepth, result);// 回溯，深度减1depth--;
}

代码

#include <iostream>
#include <climits>using namespace std;//Definition for a binary tree node.
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
public:void traversal(TreeNode* root, int depth, int& maxDepth, int& result) {// 如果当前节点是叶子节点if (root->left == nullptr && root->right == nullptr) {// 如果当前深度大于最大深度if (depth > maxDepth) {// 更新最大深度maxDepth = depth;// 更新结果值为当前节点的值result = root->val;}return;}// 如果左子节点存在if (root->left) {// 深度加1depth++;// 递归遍历左子树traversal(root->left, depth, maxDepth, result);// 回溯，深度减1depth--;}// 如果右子节点存在if (root->right) {// 深度加1depth++;// 递归遍历右子树traversal(root->right, depth, maxDepth, result);// 回溯，深度减1depth--;}return;}int findBottomLeftValue(TreeNode* root) {if (root == nullptr) {return 0;}// 记录最大深度int maxDepth = INT_MIN;// 记录最大深度最左节点的数值int result = 0;traversal(root, 0, maxDepth, result);return result;}
};int main() {Solution s;TreeNode* root = new TreeNode(3);root->left = new TreeNode(9);root->right = new TreeNode(20);root->right->left = new TreeNode(15);root->right->right = new TreeNode(7);cout << s.findBottomLeftValue(root) << endl;return 0;
}

复杂度分析

  • 时间复杂度: O(n)，其中 n 是二叉树的节点数目。需要遍历 n 个节点。
  • 空间复杂度: O(n)。递归栈需要占用 O(n) 的空间。

3、深度优先搜索（递归精简版）

思路

在回溯的地方可以进行精简，在调用traversal函数时，depth加1，在递归结束时再减1，以确保在递归的不同层次上深度值是正确的。
代码如下：
traversal(root->right, depth + 1, maxDepth, result);

代码

class Solution {
public:void traversal(TreeNode* root, int depth, int& maxDepth, int& result) {// 如果当前节点是叶子节点if (root->left == nullptr && root->right == nullptr) {// 如果当前深度大于最大深度if (depth > maxDepth) {// 更新最大深度maxDepth = depth;// 更新结果值为当前节点的值result = root->val;}return;}// 如果左子节点存在if (root->left) {// 递归遍历左子树，这里隐藏了回溯操作，在调用traversal函数时，depth加1，在递归结束时再减1traversal(root->left, depth + 1, maxDepth, result);}// 如果右子节点存在if (root->right) {// 递归遍历右子树，这里隐藏了回溯操作，在调用traversal函数时，depth加1，在递归结束时再减1traversal(root->right, depth + 1, maxDepth, result);}return;}int findBottomLeftValue(TreeNode* root) {if (root == nullptr) {return 0;}// 记录最大深度int maxDepth = INT_MIN;// 记录最大深度最左节点的数值int result = 0;traversal(root, 0, maxDepth, result);return result;}
};

复杂度分析

  • 时间复杂度: O(n)，其中 n 是二叉树的节点数目。需要遍历 n 个节点。
  • 空间复杂度: O(n)。递归栈需要占用 O(n) 的空间。

4、广度优先搜索（正向层序遍历）

思路

使用广度优先搜索遍历每一层的节点。遍历到最后一行的第一个结点就是要找的结点。

代码

class Solution {
public:int findBottomLeftValue(TreeNode* root) {// 如果根节点为空，返回0if (root == nullptr) {return 0;}// 创建一个队列用于层序遍历queue<TreeNode*> que;// 记录结果int result = 0;// 将根节点入队que.push(root);// 当队列不为空时，进行循环while (!que.empty()) {// 获取当前层的节点个数int size = que.size();// 遍历当前层的节点for (int i = 0; i < size; i++) {// 取出队首节点TreeNode* node = que.front();// 弹出队首节点que.pop();// 如果是当前层的第一个节点，更新结果if (i == 0) {result = node->val;}// 如果该节点有左子节点，将左子节点入队if (node->left) {que.push(node->left);}// 如果该节点有右子节点，将右子节点入队if (node->right) {que.push(node->right);}}}return result;}
};

复杂度分析

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

5、广度优先搜索（逆向层序遍历）

思路

使用广度优先搜索遍历每一层的节点。在遍历一个节点时，需要先把它的非空右子节点放入队列，然后再把它的非空左子节点放入队列，这样才能保证从右到左遍历每一层的节点。广度优先搜索所遍历的最后一个节点的值就是最底层最左边节点的值。

代码

class Solution {
public:int findBottomLeftValue(TreeNode* root) {// 如果根节点为空，返回0if (root == nullptr) {return 0;}// 创建一个队列用于层序遍历queue<TreeNode*> que;// 记录结果int result = 0;// 将根节点入队que.push(root);// 当队列不为空时，进行循环while (!que.empty()) {// 获取队首节点TreeNode* node = que.front();que.pop();// 如果该节点有右子节点，将右子节点入队if (node->right) {que.push(node->right);}// 如果该节点有右子节点，将右子节点入队if (node->left) {que.push(node->left);}// 更新结果为当前节点的值result = node->val;}return result;}
};

复杂度分析

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

这篇关于LeetCode 513.找树左下角的值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/978243。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
【JavaScript】LeetCode：16-20

【JavaScript】LeetCode：16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i，右指针j，从头遍历数组，若j指针指向的元素不在set中，则加入该元素，否则更新结果res，删除集合中i指针指向的元素，进入下一轮循环。 /*** @param
阅读更多...
LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵，找出只包含 1 的最大正方形，并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划
阅读更多...
LeetCode 第414场周赛个人题解

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析
阅读更多...
【JavaScript】LeetCode：21-25

【JavaScript】LeetCode：21-25

文章目录 21 最大子数组和22 合并区间23 轮转数组24 除自身以外数组的乘积25 缺失的第一个正数 21 最大子数组和 贪心 / 动态规划贪心：连续和（count）< 0时，放弃当前起点的连续和，将下一个数作为新起点，这里提供使用贪心算法解决本题的代码。动态规划：dp[i]：以nums[i]为结尾的最长连续子序列（子数组）和。 dp[i] = max(dp[i - 1]
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2