算法笔记(十三)—— 树形DP及Morris遍历
树形DP:
Question1:

以X为头结点的树,最大距离:
1. X不参与,在左子树上的最大距离
2. X不参与,在右子树上的最大距离
3. X参与,左树上最远的结点通过X到右树最远的结点
最后的结果一定是三种情况的最大值
/*** 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 Info{public:int maxdistace;int high;Info(int val1 , int val2){maxdistace = val1;high = val2;}
};class Solution {
public:Info dp(TreeNode* node){if(node==nullptr){return Info(0,0);}Info l = dp(node->left);Info r= dp(node->right);return Info(max(l.high+r.high+1 , max(l.maxdistace , r.maxdistace)) , max(l.high,r.high)+1);}int diameterOfBinaryTree(TreeNode* root) {Info res = dp(root);return res.maxdistace-1;}
};
Question2:

根据某树头结点来或不来进行分类即可
#include <iostream>
#include<bits/stdc++.h>
using namespace std;class TreeNode{
public:int num;int happy;vector<TreeNode*> nexts;TreeNode(int number , int val){num = number;happy = val;}
};class Info{
public:int inval;int outval;Info(int val1 , int val2){inval = val1;outval = val2;}
};vector<TreeNode*> Happy;Info dp(int cur){if(Happy[cur]->nexts.empty())return Info(Happy[cur]->happy , 0);int inv = Happy[cur]->happy;int outv = 0;for(auto &it:Happy[cur]->nexts){Info temp = dp(it->num);inv += temp.outval;outv += max(temp.inval , temp.outval);}return Info(inv , outv);
}int main() {int n , root;cin>>n>>root;Happy.resize(n);for(int i = 1 ; i<=n ; i++){int val;cin>>val;Happy[i-1] = new TreeNode(i-1 , val);}for(int i = 0 ; i<n-1 ; i++){int up , low;cin>>up>>low;Happy[up-1]->nexts.push_back(Happy[low-1]);}Info res = dp(root-1);cout<<max(res.inval , res.outval);return 0;
}
Morris遍历(时间复杂度O(N) 空间复杂度O(1))

前序:第一次到达一个节点的时候就打印
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;if(root==nullptr)return res;while(root!=nullptr){TreeNode* temp = root->left;if(temp!=nullptr){while(temp->right!=nullptr&&temp->right!=root){temp = temp->right;}if(temp->right==nullptr){temp->right = root;res.push_back(root->val);root = root->left;continue;}else{temp->right = nullptr;}}else{res.push_back(root->val);}root = root->right;}return res;}
};
中序:只能到达一次的节点直接打印,能到达两次的第二次打印
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;if(root==nullptr)return res;while(root!=nullptr){TreeNode* temp = root->left;if(temp!=nullptr){while(temp->right!=nullptr&&temp->right!=root){temp = temp->right;}if(temp->right==nullptr){temp->right = root;root = root->left;continue;}else{temp->right = nullptr;}}res.push_back(root->val);root = root->right;}return res;}
};
后序:第二次回到一个节点时,逆序打印该节点左子树,右边界,最后单独逆序打印整棵树右边界
class Solution {
public:TreeNode* reverse(TreeNode* root){TreeNode* pre = nullptr;TreeNode* next = nullptr;while(root!=nullptr){next = root->right;root->right = pre;pre = root;root = next;}return pre;}vector<int> postorderTraversal(TreeNode* root) {vector<int> res;TreeNode* head = root;if(root==nullptr)return res;while(root!=nullptr){TreeNode* temp = root->left;if(temp!=nullptr){while(temp->right!=nullptr&&temp->right!=root){temp = temp->right;}if(temp->right==nullptr){temp->right = root;root = root->left;continue;}else{temp->right = nullptr;TreeNode* cur = reverse(root->left);TreeNode* temp = cur;while(temp!=nullptr){res.push_back(temp->val);temp = temp->right;}root->left = reverse(cur);}}root = root->right;}TreeNode* cur = reverse(head);TreeNode* temp = cur;while(temp!=nullptr){res.push_back(temp->val);temp = temp->right;}root = reverse(cur);return res;}
};
如果一个方法需要第三次信息的强整合(向左树要信息,向右树要信息再处理),必须用递归;如果不需要,则morris遍历是最优解
相关文章:
算法笔记(十三)—— 树形DP及Morris遍历
树形DP: Question1: 以X为头结点的树,最大距离: 1. X不参与,在左子树上的最大距离 2. X不参与,在右子树上的最大距离 3. X参与,左树上最远的结点通过X到右树最远的结点 最后的结果一定是三种情况的最大…...
【Classical Network】EfficientNetV2
原文地址 原文代码 pytorch实现1 pytorch实现2 详细讲解 文章目录EfficientNet中存在的问题NAS 搜索EfficientNetV2 网络结构codeEfficientNet中存在的问题 训练图像尺寸大时,训练速度非常慢。train size 512, batch 24时,V100 out of memory在网络浅…...
索引类型FULLTEXT、NORMAL、SPATIAL、UNIQUE的区别
SQL索引的创建及使用请移步另一篇文章 (188条消息) SQL索引的创建及使用_sql索引的建立与使用_t梧桐树t的博客-CSDN博客 索引的种类 NORMAL 表示普通索引,大多数情况下都可以使用 UNIQUE 表示唯一索引,不允许重复的索引,如果该字段信息…...
稳定、可控、高可用:运维最应该加持哪些技术 buff?
如何保障开发需求高效交付,系统高峰扛得住、长期平稳,是项目组中的每位技术人必须面对的问题。 本文大纲 1、强稳定性Buff 2、风控服务实时性Buff 3、高资源利用率Buff 1.强稳定性Buff 强稳定性背后有三大挑战,其一是应对发布变更引起故障问…...
动态网站开发讲课笔记02:Java Web概述
文章目录零、本讲学习目标一、 XML基础(一)XML概述1、XML2、XML与HTML的比较(二)XML语法1、XML文档的声明2、XML元素的定义3、XML属性的定义4、XML注释的定义5、XML文件示例(三)DTD约束1、什么是XML约束2、…...
如何保护 IP 地址的隐私问题
是不是只有运营商才能查到某个人的住址信息呢?在大数据时代的今天,各种互联网应用收集了大量的数据信息,它们其实也可以根据这些信息,推断出某个人的大致地址位置。例如百度地图会一直用 App SDK 以及网页的方式记录 IP 和地址位置…...
高并发系统设计之限流
本文已收录至Github,推荐阅读 👉 Java随想录 文章目录限流算法计数器算法滑动窗口漏桶算法令牌桶算法限流算法实现Guava RateLimiter实现限流令牌预分配预热限流Nginx 限流limit_connlimit_req黑白名单限流这篇文章来讲讲限流,在高并发系统中…...
ZCMU--5286: Rose的字符串(C语言)
Description 一天Rose同学想得到一个仅由01组成的字符串S,Jack同学为了让Rose同学开心,于是打算去商店购买另一个也仅由01组成的字符串T。而商店的字符串价格由它的长度决定,比如字符串011售价3元,001011售价6元,商店…...
MAC下搭建hadoop
一:简介 Hadoop是一个用Java开发的开源框架,它允许使用简单的编程模型在跨计算机集群的分布式环境中存储和处理大数据。它的设计是从单个服务器扩展到数千个机器,每个都提供本地计算和存储。特别适合写一次,读多次的场景。 Hado…...
Python如何实现自动登录和下单的脚本,请看selenium的表演
前言 学python对selenium应该不陌生吧 Selenium 是最广泛使用的开源 Web UI(用户界面)自动化测试套件之一。Selenium 支持的语言包括C#,Java,Perl,PHP,Python 和 Ruby。目前,Selenium Web 驱动…...
华为OD机试真题Python实现【关联子串】真题+解题思路+代码(20222023)
关联子串 题目 给定两个字符串str1和str2 如果字符串str1中的字符,经过排列组合后的字符串中 只要有一个是str2的子串 则认为str1是str2的关联子串 若不是关联子串则返回-1 示例一: 输入: str1="abc",str2="efghicaibii" 输出: -1 预制条件: 输入的…...
Flutter+【三棵树】
定义 在Flutter中和Widgets一起协同工作的还有另外两个伙伴:Elements和RenderObjects;由于它们都是有着树形结构,所以经常会称它们为三棵树。 这三棵树分别是:Widget、Element、RenderObject Widget树:寄存烘托内容…...
若依系统【SpringBoot】如何集成qq邮件发送【超详细,建议收藏】
若依系统的部署博主就不在这儿阐述了,默认大家的电脑已经部署好了若依系统,这里直接开始集成邮件系统,首先我们得需要对qq邮箱进行配置;一套学不会你来打我😀; 一、开启我们的qq邮箱发送邮件的配置 1、先进…...
kettle使用--1.mysql多表关联导入mongoDB
文章目录1. 初步体验:csv 转为excelKettle概念配置mysql链接mysql 一对多关联查询结果保存到mongodb中1. 初步体验:csv 转为excel Windows环境下安装pdi-ce-8.0.0.0-28.zip ,解压后执行lib下的Spoon.bat 将csv输入拖入 双击拖进去的csv&…...
2023年CDGA考试-第10章-参考数据和主数据(含答案)
2023年CDGA考试-第10章-参考数据和主数据(含答案) 单选题 1.实现主数据中心环境的三种基本方法中不包括哪种? A.参考目录 B.注册表 C.交易中心 D.混合模式 答案 A 2.参考数据还具有很多区别于其他主数据 (例如,企业结构数据和交易结构数据)的特征。以下哪项目描述错误的…...
2023年,什么行业更有发展前景?
关于有前景有发展的行业推荐,小课今天还是推荐咱们IT互联网行业。 很多人会说现在懂电脑的那么多,这个行业都饱和了,很多学电脑的找不到工作都改行了。但事实是现在每个行各业都需要互联网,需要懂电脑的技术人才,尤其是在云计算、大数据到来…...
致盛咨询携手亚马逊云科技进一步开拓中国市场
作为医疗保健领域的咨询公司,ZS需要保证服务可靠性、敏捷性和安全性的同时,获得经济效益。亚马逊云科技丰富的云服务产品简化了ZS基础架构的搭建,为ZS节省了大量的人力与资金成本。同时,缩短了ZS扩展基础设施的周转时间࿰…...
ts之 命名空间 namespace、三斜线指令、声明文件(declare 声明ts的变量函数第三方模块等 )
目录ts之 命名空间 namespacets之 命名空间 namespacets之 三斜线指令 ( 引入其他.ts文件 )app.tsindex.tsts之 声明文件 d.ts - declare01:declare声明express第三方模块typings 为代码或者第三方模块 编写声明文件index.ts02:de…...
Day898.Join语句执行流程 -MySQL实战
Join语句执行流程 Hi,我是阿昌,今天学习记录的是关于Join语句执行流程的内容。 在实际生产中,关于 join 语句使用的问题,一般会集中在以下两类: 不让使用 join,使用 join 有什么问题呢?如果有…...
ChatGPT商业前景如何?人工智能未来会如何发展?
ChatGPT不仅在互联网和多个行业引发人们的关注,在投资界还掀起了机构对人工智能领域的投资热潮。人工智能聊天程序ChatGPT在去年11月亮相之后,在推出仅两个月后,今年1月份的月活用户已达到了1亿,成为史上增长最快的消费者应用程序…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
