【深度优先】LeetCode1932:合并多棵二叉搜索树

作者推荐

动态规划LeetCode2552：优化了6版的1324模式

题目

给你 n 个 二叉搜索树的根节点 ，存储在数组 trees 中（下标从 0 开始），对应 n 棵不同的二叉搜索树。trees 中的每棵二叉搜索树 最多有 3 个节点 ，且不存在值相同的两个根节点。在一步操作中，将会完成下述步骤：
选择两个 不同的 下标 i 和 j ，要求满足在 trees[i] 中的某个 叶节点 的值等于 trees[j] 的 根节点的值 。
用 trees[j] 替换 trees[i] 中的那个叶节点。
从 trees 中移除 trees[j] 。
如果在执行 n - 1 次操作后，能形成一棵有效的二叉搜索树，则返回结果二叉树的 根节点 ；如果无法构造一棵有效的二叉搜索树，返回 null 。
二叉搜索树是一种二叉树，且树中每个节点均满足下述属性：
任意节点的左子树中的值都 严格小于 此节点的值。
任意节点的右子树中的值都 严格大于 此节点的值。
叶节点是不含子节点的节点。
示例 1：
输入：trees = [[2,1],[3,2,5],[5,4]]
输出：[3,2,5,1,null,4]
解释：
第一步操作中，选出 i=1 和 j=0 ，并将 trees[0] 合并到 trees[1] 中。
删除 trees[0] ，trees = [[3,2,5,1],[5,4]] 。
在第二步操作中，选出 i=0 和 j=1 ，将 trees[1] 合并到 trees[0] 中。
删除 trees[1] ，trees = [[3,2,5,1,null,4]] 。
结果树如上图所示，为一棵有效的二叉搜索树，所以返回该树的根节点。
示例 2：
输入：trees = [[5,3,8],[3,2,6]]
输出：[]
解释：
选出 i=0 和 j=1 ，然后将 trees[1] 合并到 trees[0] 中。
删除 trees[1] ，trees = [[5,3,8,2,6]] 。
结果树如上图所示。仅能执行一次有效的操作，但结果树不是一棵有效的二叉搜索树，所以返回 null 。
示例 3：
输入：trees = [[5,4],[3]]
输出：[]
解释：无法执行任何操作。
参数范围：
n == trees.length
1 <= n <= 5 * 104
每棵树中节点数目在范围 [1, 3] 内。
输入数据的每个节点可能有子节点但不存在子节点的子节点
trees 中不存在两棵树根节点值相同的情况。
输入中的所有树都是 有效的二叉树搜索树 。
1 <= TreeNode.val <= 5 * 104.

分析

正确分析

能合并则合并，如果合并树的数量为1，则正确。
不需要考虑：叶子相同，那个叶子合并根的问题，两个叶子相同，那个叶子合并最后都不会是合法的搜索树。

错误分析

vMin 记录各子树的最小值，vMax记录各子树的最大值。 成为左子树的条件：一，叶子的值等子树根的值。 二，子树的最大值小于父树的值。成为右子树的条件：一，叶子的值等子树根的值。 二，子树的最小值大于父树的值。

错误原因

父子符合条件，祖孙不符合条件。

解决方法

判断是否是合法的树。

变量解释

vMin[i]以trees[i]为根的树的最小节点值
vMax[i]以trees[i]为根的树的最大节点值
mValueIndexkey:trees[i]根节点的值；value:i。

代码

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* canMerge(vector<TreeNode*>& trees) {
m_c = trees.size();
vector vMin(m_c), vMax(m_c);
unordered_map<int, int> mValueIndex;
for (int i = 0; i < m_c; i++)
{
const auto& p = trees[i];
mValueIndex[p->val] = i;
vMin[i] = (nullptr == p->left) ? p->val : p->left->val;
vMax[i] = (nullptr == p->right) ? p->val : p->right->val;
}
for (int i = 0; i < m_c; i++)
{
std::cout << "i " << i;
const auto& p = trees[i];
if ((nullptr != p->left) && mValueIndex.count(p->left->val))
{
const int index = mValueIndex[p->left->val];
if (vMax[index] < p->val)
{
std::cout << "index " << index;
vMin[i] = min(vMin[i], vMin[index]);
p->left = trees[index];
mValueIndex.erase(mValueIndex.find(p->left->val));
}
}
if ((nullptr != p->right) && mValueIndex.count(p->right->val))
{
const int index = mValueIndex[p->right->val];
if (vMin[index] > p->val)
{
std::cout << "r " << index;
vMax[i] = max(vMax[i], vMax[index]);
p->right = trees[index];
mValueIndex.erase(p->right->val);
}
}
std::cout << std::endl;
}
if (mValueIndex.size() > 1) return nullptr;
auto [suc, tmp1, tmp2] = DFS(trees[mValueIndex.begin()->second]);
if (!suc)
{
return nullptr;
}
return trees[mValueIndex.begin()->second];
}
std::tuple<bool, int, int> DFS(TreeNode* root)
{
int iMin = root->val;
int iMax = root->val;
if (nullptr != root->left)
{
auto [suc, iRetMin, iRetMax] = DFS(root->left);
if ((!suc)||( iRetMax >= root->val))
{
return std::make_tuple(false, 0, 0);
}
iMin = iRetMin;
}
if (nullptr != root->right)
{
auto [suc, iRetMin, iRetMax] = DFS(root->right);
if ((!suc) || (iRetMin <= root->val))
{
return std::make_tuple(false, 0, 0);
}
iMax = iRetMax;
}
return std::make_tuple(true, iMin, iMax);
}
int m_c;
};

优化

分析

最后总是要判断是否是合法树，那合并树的时候就不需要判断了。这样会产生新问题：
三个子树成环，两个子树合并成树。 合并了3次符合条件，但不是一棵树，而是两个连通区域。
解法方法如下：
一，判断唯一的树的节点数是否合法。
二，并集查找，看有几个连通区域。
三，判断有几个合法的根（不存在值相同的叶子），从根开始合并。
四，获取树的中顺遍历，看是否是严格递增。且节点数是否正确。

判断合法的根的代码

class Solution {
public:
TreeNode* canMerge(vector<TreeNode*>& trees) {
m_c = trees.size();
unordered_set setLeaf;
for (int i = 0; i < m_c; i++)
{
auto& p = trees[i];
m_mValuePtr[p->val] = p;
if (nullptr != p->left)
{
setLeaf.emplace(p->left->val);
}
if (nullptr != p->right)
{
setLeaf.emplace(p->right->val);
}
}
TreeNode* root = nullptr;
for (int i = 0; i < m_c; i++)
{
if (setLeaf.count(trees[i]->val))
{
continue;//和某个叶子起点重合，不是根
}
if (nullptr != root)
{
return nullptr;//不可能有两个根
}
root = trees[i];
}
if( nullptr == root)
{
return nullptr;
}
DFSBuild(root);
if (m_mValuePtr.size() != 1 )
{
return nullptr;
}
auto [suc, tmp1, tmp2] = DFS(root);
if (!suc)
{
return nullptr;
}
return root;
}
void DFSBuild(TreeNode* root)
{
auto Build = [&](TreeNode*& node)
{
if ((nullptr != node) && (m_mValuePtr.count(node->val)))
{
node = m_mValuePtr[node->val];
m_mValuePtr.erase(node->val);
DFSBuild(node);
}
};
Build(root->left);
Build(root->right);
}
std::tuple<bool, int, int> DFS(TreeNode* root)
{
int iMin = root->val;
int iMax = root->val;
if (nullptr != root->left)
{
auto [suc, iRetMin, iRetMax] = DFS(root->left);
if ((!suc) || (iRetMax >= root->val))
{
return std::make_tuple(false, 0, 0);
}
iMin = iRetMin;
}
if (nullptr != root->right)
{
auto [suc, iRetMin, iRetMax] = DFS(root->right);
if ((!suc) || (iRetMin <= root->val))
{
return std::make_tuple(false, 0, 0);
}
iMax = iRetMax;
}
return std::make_tuple(true, iMin, iMax);
}
unordered_map<int, TreeNode*> m_mValuePtr;
int m_c;
};

中序遍历

class Solution {
public:
TreeNode* canMerge(vector<TreeNode*>& trees) {
m_c = trees.size();
int iNodeCount = 0;
for (int i = 0; i < m_c; i++)
{
const auto& p = trees[i];
m_mValuePtr[p->val] = p;
iNodeCount += (1 + (nullptr != p->left) + (nullptr != p->right));
}
for (int i = 0; i < m_c; i++)
{
auto Build = [&](TreeNode*& node)
{
if ((nullptr != node) && (m_mValuePtr.count(node->val)))
{
node = m_mValuePtr[node->val];
m_mValuePtr.erase(node->val);
}
};
Build(trees[i]->left);
Build(trees[i]->right);
}
if (m_mValuePtr.size() != 1 )
{
return nullptr;
}
vector vNode;
DFSNLR(vNode, m_mValuePtr.begin()->second);
if (vNode.size() + m_c-1 != iNodeCount)
{
return nullptr;
}
for (int i = 1; i < vNode.size(); i++)
{
if (vNode[i] <= vNode[i - 1])
{
return nullptr;
}
}
return m_mValuePtr.begin()->second;
}
void DFSNLR(vector& v,TreeNode* root)
{
if (nullptr == root)
{
return ;
}
DFSNLR(v,root->left);
v.emplace_back(root->val);
DFSNLR(v,root->right);
}
unordered_map<int, TreeNode*> m_mValuePtr;
int m_c;
};

中序遍历优化

vNode我们只需要读取最后一个值，所以可以用一个整形变量pre代替。

 class Solution {public:TreeNode* canMerge(vector<TreeNode*>& trees) {m_c = trees.size();int iNodeCount = 0;for (int i = 0; i < m_c; i++){const auto& p = trees[i];m_mValuePtr[p->val] = p;iNodeCount += (1 + (nullptr != p->left) + (nullptr != p->right));}for (int i = 0; i < m_c; i++){auto Build = [&](TreeNode*& node){if ((nullptr != node) && (m_mValuePtr.count(node->val))){node = m_mValuePtr[node->val];m_mValuePtr.erase(node->val);		}};Build(trees[i]->left);Build(trees[i]->right);}if (m_mValuePtr.size() != 1 ){return  nullptr;}int pre=-1;if (!DFSNLR(m_mValuePtr.begin()->second, pre) || (m_iNodeSize + m_c - 1 != iNodeCount)){return nullptr;}return m_mValuePtr.begin()->second;}bool DFSNLR(TreeNode* root, int& pre){if ((root->left) && (!DFSNLR(root->left, pre))){return false;}m_iNodeSize++;if (root->val <= pre){return false;}pre = root->val;if ((root->right) && (!DFSNLR(root->right, pre))){return false;}return true;}	   int m_iNodeSize = 0;unordered_map<int, TreeNode*> m_mValuePtr;int m_c;};

2023年6月旧版

class Solution {
public:
TreeNode* canMerge(vector<TreeNode*>& trees) {
vector<TreeNode*> vRoot(5 * 10000 + 1);
std::set setNums;
for (auto& ptr : trees)
{
vRoot[ptr->val] = ptr;
setNums.emplace(ptr->val);
if (nullptr != ptr->left)
{
setNums.emplace(ptr->left->val);
}
if (nullptr != ptr->right)
{
setNums.emplace(ptr->right->val);
}
}
int iNodeNum = setNums.size();
for (auto& ptr : trees)
{
if ((nullptr != ptr->left) && (nullptr != vRoot[ptr->left->val]))
{
ptr->left = vRoot[ptr->left->val];
vRoot[ptr->left->val] = nullptr;
}
if ((nullptr != ptr->right) && (nullptr != vRoot[ptr->right->val]))
{
ptr->right = vRoot[ptr->right->val];
vRoot[ptr->right->val] = nullptr;
}
}
TreeNode* pRoot = nullptr;
for (auto ptr : vRoot)
{
if (nullptr == ptr)
{
continue;
}
if (nullptr != pRoot)
{
return nullptr;//两个根
}
pRoot = ptr;
}
if (nullptr == pRoot)
{
return nullptr;
}
if (iNodeNum != DFSNum(pRoot))
{
return nullptr;
}
int iMin, iMax;
bool bRet = DFS(iMin, iMax, pRoot);
return bRet ? pRoot : nullptr;
}
bool DFS(int& iMin, int& iMax, TreeNode* pNode)
{
iMin = iMax = pNode->val;
if ((nullptr != pNode->left))
{
int iMinLeft, iMaxLeft;
if (!DFS(iMinLeft, iMaxLeft, pNode->left))
{
return false;
}
if (iMaxLeft >= pNode->val)
{
return false;
}
iMin = iMinLeft;
}
if ((nullptr != pNode->right))
{
int iMinRight, iMaxRight;
if (!DFS(iMinRight, iMaxRight, pNode->right))
{
return false;
}
if (iMinRight <= pNode->val)
{
return false;
}
iMax = iMaxRight;
}
return true;
}
int DFSNum(TreeNode* pNode)
{
if (nullptr == pNode)
{
return 0;
}
return 1 + DFSNum(pNode->left) + DFSNum(pNode->right);
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：

VS2022 C++17

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/207844.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

HarmonyOS4.0 ArkUI组件

HarmonyOS4.0 ArkUI组件

目录 简介 搭建开发环境 ArkUI基础组件 Image组件 Text组件 TextInput Button Slider 简介 HarmonyOS 4.0的ArkUI组件是一套UI开发框架&#xff0c;提供开发者进行应用UI开发时所必须的能力。在ArkUI中&#xff0c;组件是界面搭建与显示的最小单位&#xff0c;开发者通过…
阅读更多...
Normalizing Kalman Filters for Multivariate Time Series Analysis

Normalizing Kalman Filters for Multivariate Time Series Analysis

l l l means latent state&#xff0c;LGM means ‘linear Gaussian state space models’ 辅助信息 作者未提供代码
阅读更多...
pip包管理工具

pip包管理工具

pip 是 Python 包管理工具&#xff0c;该工具提供了对Python包的查找、下载、安装、卸载的功能。 Python 2.7.9 或 Python 3.4 以上版本的python都自带 pip 工具 1. 配置pip国内镜像 pip安装的包都存在于外国的服务器上&#xff0c;速度会非常慢&#xff0c;可以给pip配置国内…
阅读更多...
优彩云采集器最新版免费下载，优彩云采集器免费

优彩云采集器最新版免费下载，优彩云采集器免费

随着网络时代的发展&#xff0c;SEO&#xff08;Search Engine Optimization&#xff0c;搜索引擎优化&#xff09;已经成为网站推广和营销的关键一环。在SEO的世界里&#xff0c;原创内容的重要性愈发凸显。想要做到每天更新大量原创文章&#xff0c;并不是一件轻松的事情。优…
阅读更多...
排序算法：n个0~1000之间的整数，将他们从大到小排序

排序算法：n个0~1000之间的整数，将他们从大到小排序

上榜理由&#xff1a; 如果没见过这种排序题&#xff0c;可能首先想到的就是常用的排序算法&#xff0c;比如快速排序&#xff0c;归并排序&#xff0c;那如果输入的n足够大&#xff0c;时间复杂度肯定比较高。其实题目0-1000的范围是一个题眼&#xff0c;所以一定有更优的排序…
阅读更多...
国内哪个超声波清洗机品牌比较好？质量好超声波清洗机总结

国内哪个超声波清洗机品牌比较好？质量好超声波清洗机总结

近年来超声波清洗机可以说是非常火爆&#xff0c;可以清洗化妆刷、眼镜、牙套等等一些小物件&#xff0c;大物件物品可以入手大型超声波清洗机&#xff0c;总之现在超声波清洗机已经衍生到可以在家使用&#xff0c;不再是在眼镜店看到它的身影或者是一些工业领域上&#xff0c;…
阅读更多...
FL Studio2024重磅更新 带你了解FL21.2最新版本功能

FL Studio2024重磅更新 带你了解FL21.2最新版本功能

FL Studio2024是功能强大的音乐制作解决方案&#xff0c;使用旨在为用户提供一个友好完整的音乐创建环境&#xff0c;让您能够轻松创建、管理、编辑、混合具有专业品质的音乐&#xff0c;一切的一切都集中在一个软件中&#xff0c;只要您想&#xff0c;只要您需要&#xff0c;它…
阅读更多...
clip-path，css裁剪函数

clip-path，css裁剪函数

https://www.cnblogs.com/dzyany/p/13985939.html clip-path - CSS&#xff1a;层叠样式表 | MDN 我们看下这个例子 polygon里有四个值分别代表这四个点相对于原图左上方的偏移量。 裁剪个五角星
阅读更多...
六、ZooKeeper Java API操作

六、ZooKeeper Java API操作

目录 1、引入maven坐标 2、节点的操作 这里操作Zookeeper的JavaAPI使用的是一套zookeeper客户端框架 Curator ，解决了很多Zookeeper客户端非常底层的细节开发工作 。 Curator包含了几个包：
阅读更多...
ansible模块

ansible模块

目录 一、ansible的command模块 1.ad-hoc 2.playbook 3.command模块 二、ansible的shell模块 1.shell模块帮助 2.shell模块支持的参数和解释 3.简单试验 4.批量远程执行脚本 三、script模块 1.script模块帮助 2.shell模块支持的参数和解释 3.实践 四、ansible文件…
阅读更多...
【学习记录】从0开始的Linux学习之旅——应用开发（helloworld）

【学习记录】从0开始的Linux学习之旅——应用开发（helloworld）

一、概述 Linux操作系统通常是基于Linux内核&#xff0c;并结合GNU项目中的工具和应用程序而成。Linux操作系统支持多用户、多任务和多线程&#xff0c;具有强大的网络功能和良好的兼容性。本文主要讲述如何在linux系统上进行应用开发。 二、概念及原理 应用程序通过系统调用与…
阅读更多...
Jmeter工具+ant+jenkins实现持续集成

Jmeter工具+ant+jenkins实现持续集成

jmeterantjenkins持续集成 一、下载并配置jmeter 首先下载jmeter工具&#xff0c;并配置好环境变量&#xff1b;参考&#xff1a; jmeter默认保存的是.jtl格式的文件&#xff0c;要设置一下bin/jmeter.properties,文件内容&#xff0c;保存jmeter.save.saveservice.output_f…
阅读更多...
【CVE-2023-49103】ownCloud graphapi信息泄露漏洞（2023年11月发布）

【CVE-2023-49103】ownCloud graphapi信息泄露漏洞（2023年11月发布）

漏洞简介 ownCloud owncloud/graphapi 0.2.x在0.2.1之前和0.3.x在0.3.1之前存在漏洞。graphapi应用程序依赖于提供URL的第三方GetPhpInfo.php库。当访问此URL时&#xff0c;会显示PHP环境的配置详细信息&#xff08;phpinfo&#xff09;。此信息包括Web服务器的所有环境变量&a…
阅读更多...
3.3 路由器的远程配置

3.3 路由器的远程配置

实验3.3 路由器的远程配置 一、任务描述二、任务分析三、具体要求四、实验拓扑五、任务实施&#xff08;一&#xff09;、配置通过Telnet登录系统1.RA的基本配置2.RB的基本配置3.在RA上配置Telnet用户登录界面 &#xff08;二&#xff09;、配置通过STelnet登录系统1.RA的基本配…
阅读更多...
MySQL的系统信息函数

MySQL的系统信息函数

系统信息函数让你更好的使用MySQL数据库 1、version()函数 查看MySQL系统版本信息号 select version();2、connection_id()函数 查看当前登入用户的连接次数 直接调用CONNECTION_ID()函数--不需任何参数--就可以看到当下连接MySQL服务器的连接次数&#xff0c;不同时间段该…
阅读更多...
Sentinel核心类解读：Node

Sentinel核心类解读：Node

基本介绍 Sentinel中的簇点链路是由一个个的Node组成的&#xff0c;Node是一个接口。Node中保存了对资源的实时数据的统计&#xff0c;Sentinel中的限流或者降级等功能就是通过Node中的数据进行判断的。 Sentinel中是这样描述Node的&#xff1a; Holds real-time statistics…
阅读更多...
C++基础 -28- 友元

C++基础 -28- 友元

友元用于访问类中的所有数据成员 类中的私有成员&#xff0c;类外不可访问 定义友元的格式&#xff08;友元函数必须要在类内&#xff0c;声明&#xff09; friend void show(person &b); 使用友元访问类的所有成员 #include "iostream"using namespace std…
阅读更多...
MySQL之性能分析和系统调优

MySQL之性能分析和系统调优

MySQL之性能分析和系统调优 性能分析 查看执行计划 EXPLAIN EXPLAIN作为MySQL的性能分析神器&#xff0c;可以用来分析SQL执行计划&#xff0c;需要理解分析结果可以帮助我们优化SQL explain select … from … [where ...]TABLE 表名 查询的每一行记录都对于着一张表 id 该…
阅读更多...
什么是路由抖动？该如何控制

什么是路由抖动？该如何控制

路由器在实现不间断的网络通信和连接方面发挥着重要作用&#xff0c;具有所需功能的持续可用的路由器可确保其相关子网的良好性能&#xff0c;由于网络严重依赖路由器的性能&#xff0c;因此确保您的路由器不会遇到任何问题非常重要。路由器遇到的一个严重的网络问题是路由抖动…
阅读更多...
分布式ID生成框架Leaf升级踩坑

分布式ID生成框架Leaf升级踩坑

背景&#xff1a; 在项目中需要一个统一的拿单号等唯一ID的服务&#xff0c;就想起了之前用到的leaf&#xff0c;但是因为项目要求&#xff0c;leaf的版本不符合&#xff0c;需要做一些升级 项目地址&#xff1a;https://github.com/Meituan-Dianping/Leaf 升级点&#xff1…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023