算法学习——LeetCode力扣二叉树篇5

news/2024/4/25 19:24:39

算法学习——LeetCode力扣二叉树篇5

在这里插入图片描述

513. 找树左下角的值

513. 找树左下角的值 - 力扣(LeetCode)

描述

给定一个二叉树的 根节点 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

代码解析

程序遍历法
/*** 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:int findBottomLeftValue(TreeNode* root) {int result;queue<TreeNode*> my_queue;if(root==nullptr) return result;my_queue.push(root);while(my_queue.empty() != 1){int size = my_queue.size();for(int i=0 ; i<size ; i++){TreeNode* cur = my_queue.front();my_queue.pop();//每一列的左子叶都加入,最后结果就是最后的左子叶if(i==0&&cur->left==nullptr&&cur->right==nullptr) result = cur->val;if(cur->left != nullptr) my_queue.push(cur->left);if(cur->right != nullptr) my_queue.push(cur->right);}}return result;}
};
递归法
/*** 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:int maxDepth = INT_MIN;int result;void traversal(TreeNode* root, int depth) {if (root->left == NULL && root->right == NULL) {//记录第一次遇见的大深度叶子,就是最左叶子//必须是> 不能是>=if (depth > maxDepth) {maxDepth = depth;result = root->val;}return;}if (root->left) {traversal(root->left, depth + 1); // 隐藏着回溯}if (root->right) {traversal(root->right, depth + 1); // 隐藏着回溯}return;}int findBottomLeftValue(TreeNode* root) {traversal(root, 0);return result;}
};

112. 路径总和

112. 路径总和 - 力扣(LeetCode)

描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

叶子节点 是指没有子节点的节点。

示例

示例 1:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。

示例 2:

输入:root = [1,2,3], targetSum = 5
输出:false
解释:树中存在两条根节点到叶子节点的路径:
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3:

输入:root = [], targetSum = 0
输出:false
解释:由于树是空的,所以不存在根节点到叶子节点的路径。

提示

  • 树中节点的数目在范围 [0, 5000] 内
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

代码解析

/*** 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:bool result = false;void getsum(TreeNode* cur, int targetSum , int sum){if(cur==nullptr)return;sum += cur->val;//找到叶子节点的和与目标相符if(cur->left==nullptr && cur->right==nullptr &&sum == targetSum) result = true;getsum(cur->left,  targetSum ,  sum);getsum(cur->right,  targetSum ,  sum);}bool hasPathSum(TreeNode* root, int targetSum) {if(root==nullptr) return false;getsum(root , targetSum , 0);return result;}
};

106. 从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)

描述

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

示例

示例 1:

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]

示例 2:

输入:inorder = [-1], postorder = [-1]
输出:[-1]

提示

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

代码解析

通过后序的最后找中间点,然后去分割中序,得到左右子树

/*** 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:TreeNode* get_tree(vector<int>& inorder, vector<int>& postorder){//如果中序数组或者后序数组是空,就返回空节点if(inorder.size()==0||postorder.size()==0) return nullptr;//后续数组的最后一个是根节点。TreeNode* root = new TreeNode(postorder[postorder.size()-1]);//根据根节点的值,去找到对应的中序根节点int root_num ;for(int i= 0 ;i<inorder.size();i++){if(inorder[i] == root->val){root_num = i;break;}}//通过中序数组中根节点的位置,根节点前面是左子树,后面是右子树vector<int> inorder_left(inorder.begin() , inorder.begin()+root_num);vector<int> inorder_right(inorder.begin()+root_num+1 , inorder.end());//通过中序分割出左子树和右子树的长度,去分割后续数组的左子树和右子树vector<int> postorder_left(postorder.begin() , postorder.begin() + inorder_left.size());vector<int> postorder_right(postorder.begin()+ inorder_left.size() , postorder.end()-1);//然后递归迭代,左子树的中序和后续,右子树的中序和后续root->left =  get_tree(inorder_left , postorder_left);root->right = get_tree(inorder_right , postorder_right );//返归根节点return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {//如果输入两个数组是空,则返回空节点if(inorder.size()==0||postorder.size()==0) return nullptr;return get_tree(inorder, postorder);}
};

654. 最大二叉树

654. 最大二叉树 - 力扣(LeetCode)

描述

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点,其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。

示例

示例 1:

输入:nums = [3,2,1,6,0,5]
输出:[6,3,5,null,2,0,null,null,1]
解释:递归调用如下所示:

  • [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。
    • [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。
      • 空数组,无子节点。
      • [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。
        • 空数组,无子节点。
        • 只有一个元素,所以子节点是一个值为 1 的节点。
    • [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。
      • 只有一个元素,所以子节点是一个值为 0 的节点。
      • 空数组,无子节点。

示例 2:

输入:nums = [3,2,1]
输出:[3,null,2,null,1]

提示

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
  • nums 中的所有整数 互不相同

代码解析

/*** 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:TreeNode* get_big_tree(vector<int>& nums){if(nums.size() == 0) return nullptr;TreeNode* root = new TreeNode;auto max_val =  max_element(nums.begin() , nums.end());root->val = *max_val;// cout<<*max_val<<' '<<max_val - nums.begin()<<endl;vector<int> left_nums(nums.begin() ,   max_val );vector<int> right_nums(  max_val  + 1 , nums.end());root->left = get_big_tree(left_nums);root->right = get_big_tree(right_nums);return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.size() == 0) return nullptr;return get_big_tree(nums);}
};

https://www.xjx100.cn/news/3271242.html

相关文章

C# CAD交互界面-自定义面板集-查找定位(六)

运行环境 vs2022 c# cad2016 调试成功 一、代码说明 1. 类成员变量声明&#xff1a; List<ObjectId> objectIds new List<ObjectId>(); // 用于存储AutoCAD实体对象的ObjectId列表 private static Autodesk.AutoCAD.Windows.PaletteSet _ps2; // 自定义浮动面板…

2024年教师资格证认定报名完整流程

&#x1f49a;网上报名流程概览 一、进入教资认定网报入口&#xff1b; 二、进行实名核验&#xff1b; 三、申请网报时间查询&#xff1b; 四、个人信息维护&#xff1b; 五、认定申请报名&#xff1b; &#x1f49a;认定所需材料 1、 身份证&#xff1b; 2 、户口本/居住证…

nba2k24 韩旭面补

nba2k23-24 韩旭面补 nba2k23-nba2k24通用 韩旭面补 下载地址&#xff1a; https://www.changyouzuhao.cn/9605.html

使用Docker快速部署MySQL

部署MySQL 使用Docker安装&#xff0c;仅仅需要一步即可&#xff0c;在命令行输入下面的命令 docker run -d \--name mysql \-p 3306:3306 \-e TZAsia/Shanghai \-e MYSQL_ROOT_PASSWORD123456 \mysql MySQL安装完毕&#xff01;通过任意客户端工具即可连接到MySQL. 当我们执…

车载诊断协议DoIP系列 —— 协议中的简易网络拓扑概述

车载诊断协议DoIP系列 —— 协议中的简易网络拓扑概述 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师(Wechat:gongkenan2013)。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 本就是小人物,输了就是输了,不要在意别人怎么看自己。江湖一碗…

论气质,咱就没输过谁—高级感或许是网站建设的救赎之路。

大千UI工场经常帮客户优化和开发网站&#xff0c;现在客户对网站的要求越来越高&#xff0c;本文分享我们的一些实践经验。 不可否认&#xff0c;随着自媒体的兴起&#xff0c;官网赖以生存的流量池&#xff08;搜索引擎&#xff09;被自媒体分流了很多。从近期所承接的官网项目…

【MATLAB】GA_BP神经网络回归预测算法

有意向获取代码&#xff0c;请转文末观看代码获取方式~也可转原文链接获取~ 1 基本定义 GA_BP神经网络回归预测算法结合了遗传算法&#xff08;Genetic Algorithm, GA&#xff09;和BP神经网络&#xff08;Backpropagation Neural Network, BPNN&#xff09;&#xff0c;用于解…

漫漫数学之旅018

文章目录 经典格言数学习题古今评注名人小传 - 库尔特哥德尔 经典格言 一个毫无自由的社会——一个人凡事都要遵循严格统一的规则——将在行为上既不一致也不完全&#xff0c;甚至不能解决某些也许很重要的问题。——库尔特哥德尔&#xff08;Kurt Gdel&#xff09; 库尔特哥德…