【深度优先】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

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

程序猿无烦恼：让养生专家来写代码！！！

程序猿无烦恼：让养生专家来写代码！！！

自己的经验&#xff0c;也是看旁边焦虑的开发总结的一些经验&#xff0c;讲道理不一定有用&#xff0c;但是道理本身一定是对的。 文章目录 持续学习少烦恼明确需求少问题少盯荧幕多冥想少吃奶茶多锻炼亲近自然要放空 持续学习少烦恼 C、JAVA、python、数据库…… 唯有持续学…
阅读更多...
Docker下安装Tomcat

Docker下安装Tomcat

目录 Tomcat简介 Tomcat安装 免修改版Tomcat安装 Tomcat简介 Tomcat是Apache软件基金会&#xff08;Apache Software Foundation&#xff09;的Jakarta 项目中的一个核心项目&#xff0c;由Apache、Sun 和其他一些公司及个人共同开发而成。由于有了Sun 的参与和支持&#x…
阅读更多...
LeetCode | 965. 单值二叉树

LeetCode | 965. 单值二叉树

LeetCode | 965. 单值二叉树 OJ链接 首先判断树为不为空&#xff0c;为空直接true然后判断左子树的val&#xff0c;和根的val相不相同再判断右子树的val&#xff0c;和根的val相不相同最后递归左子树和右子树 bool isUnivalTree(struct TreeNode* root) {if(root NULL)retur…
阅读更多...
8通道16位数据采集卡方案

8通道16位数据采集卡方案

硬件方案--采集板 下载链接&#xff01;https://mp.weixin.qq.com/s?__bizMzU2OTc4ODA4OA&mid2247558420&idx1&sn3b1d6a99a69e68c32f425e489c21b6d5&chksmfcfaf6c3cb8d7fd52961827dedf30a79e65ed96e5b507bc5027d80f9285aa9bdcf790b940b51&token1650944467…
阅读更多...
C/C++ 内存管理（1）

C/C++ 内存管理（1）

文章目录 C/C 内存划分静态和动态内存C语言的动态内存分配函数mallocfreecallocrealloc 常见内存使用错误 C/C 内存划分 栈区&#xff08;stack&#xff09;&#xff1a;在执行函数时&#xff0c;函数内局部变量的存储单元都可以在栈上创建&#xff0c;函数执行结 束时这些存储…
阅读更多...
92基于matlab的引力搜索算法优化支持向量机（GSA-SVM）分类模型

92基于matlab的引力搜索算法优化支持向量机（GSA-SVM）分类模型

基于matlab的引力搜索算法优化支持向量机&#xff08;GSA-SVM&#xff09;分类模型&#xff0c;以分类精度为优化目标优化SVM算法的参数c和g&#xff0c;输出分类可视化结果及适应度变化曲线。数据可更换自己的&#xff0c;程序已调通&#xff0c;可直接运行。 92 引力搜索算法…
阅读更多...
mysql的InnoDB存储引擎

mysql的InnoDB存储引擎

详情请参考&#xff1a;https://dev.mysql.com/doc/refman/8.0/en/innodb-storage-engine.html InnoDB 是一个通用目的的存储引擎&#xff0c;它在高可用性、高性能方面做了平衡。MySQL 8.0&#xff0c;InnoDB 是默认的存储引擎。在创建表的时候&#xff0c;如果没有使用ENGIN…
阅读更多...
vmware 安装 AlmaLinux OS 8.6

vmware 安装 AlmaLinux OS 8.6

选择系统镜像 选择镜像 选择安装位置和修改名称 可以自定义硬件&#xff0c;也可以不选择&#xff0c;后面可以再设置 自定义硬件可以设置内存和cpu等信息 安装虚拟机系统 密码如果简单的话需要点击两次done 才能保存
阅读更多...
STM32 定时器TIM

STM32 定时器TIM

单片机学习 目录 文章目录 前言 一、TIM简介 二、STM32的三种定时器 2.1基本定时器 2.1.1定时中断功能 1. 时钟源 2. 预分频器 3. 计数器 4. 自动重装寄存器 5.更新中断和更新事件 2.1.2主模式触发DAC功能 2.2 计数模式 2.2通用定时器 2.2.1 时钟源 外部时钟模式2 外部时钟模式…
阅读更多...
使用PCReg.PyTorch项目训练自己的数据集进行点云配准

使用PCReg.PyTorch项目训练自己的数据集进行点云配准

项目地址&#xff1a; https://github.com/zhulf0804/PCReg.PyTorch/tree/main 网络简介&#xff1a; 网络是基于PointNet Concat FC的&#xff0c;它没有其它复杂的结构&#xff0c;易于复现。因其简洁性&#xff0c;这里暂且把其称作点云配准的Benchmark。因作者源码中复杂…
阅读更多...
项目实战之RabbitMQ死信队列应用

项目实战之RabbitMQ死信队列应用

&#x1f9d1;‍&#x1f4bb;作者名称&#xff1a;DaenCode &#x1f3a4;作者简介&#xff1a;啥技术都喜欢捣鼓捣鼓&#xff0c;喜欢分享技术、经验、生活。 &#x1f60e;人生感悟&#xff1a;尝尽人生百味&#xff0c;方知世间冷暖。 文章目录 &#x1f31f;架构图&#x…
阅读更多...
SpringMVC入门详解

SpringMVC入门详解

SpringMVC概述 开始之前了解一下三层架构 在JavaEE中我们现在几乎全用的是B/S架构&#xff0c;也就是浏览器 / 服务器架构&#xff0c;在B/S架构中&#xff0c;系统包括标准的三层架构模式&#xff1a; 1.web层&#xff08;表现层&#xff09; 它负责接收客户端请求&#x…
阅读更多...
SIP协议在语音通信的应用方式及OKCC系统中的配置方法

SIP协议在语音通信的应用方式及OKCC系统中的配置方法

在企业语音通信的过程中&#xff0c;SIP协议支持的网络通信技术通过网络为用户提供了无数的通信便利&#xff0c;已成为企业不可或缺的重要通信技术。由于SIP协议是语音通信帮助企业实现这些优势的原因&#xff0c;因此了解支持这些呼叫的SIP协议的上下文至关重要。 什么是SI…
阅读更多...
服务器和Linux ，安装R rstudio ，常用软件

服务器和Linux ，安装R rstudio ，常用软件

服务器的基本概念&#xff1a; 如服务器的基本结构&#xff0c;节点&#xff0c;端口的概念等。 服务器的基本设置和管理&#xff1a; 如何配置新服务器&#xff0c; 如何管理服务器&#xff0c;如何分配账户并确保他们互不访问&#xff0c; 如何全局安装软件让所有人都可以…
阅读更多...
【数据结构】 堆排序与TopK问题详解

【数据结构】 堆排序与TopK问题详解

在学习完堆的创建后&#xff0c;就轮到了标题的两个问题 这两个问题在实际生活中会有比较强的实际问题解决能力 先分别解释一下 堆排序&#xff1a; 运用堆的思想进行排序&#xff0c;时间复杂度为O(NlogN)TopK&#xff1a; 从一大堆数据中选择K个最大或最小的数据&#xff0c…
阅读更多...
如何本地搭建个人hMailServer邮件服务并实现远程发送邮件

如何本地搭建个人hMailServer邮件服务并实现远程发送邮件

文章目录 前言1. 安装hMailServer2. 设置hMailServer3. 客户端安装添加账号4. 测试发送邮件5. 安装cpolar6. 创建公网地址7. 测试远程发送邮件8. 固定连接公网地址9. 测试固定远程地址发送邮件 前言 hMailServer 是一个邮件服务器,通过它我们可以搭建自己的邮件服务,通过cpola…
阅读更多...
了解c语言中的结构体

了解c语言中的结构体

介绍&#xff1a; 在C语言中&#xff0c;结构体是一种用户自定义的数据类型&#xff0c;它允许我们将不同类型的数据组合在一起&#xff0c;形成一个更为复杂的数据结构。结构体可以用来表示现实世界中的实体&#xff0c;如人员、学生、图书等。本篇博客将介绍结构体的基本概念…
阅读更多...
Postgresql分区表

Postgresql分区表

PostgreSQL 提供了三种分区表实现方式&#xff1a; range &#xff1a;范围分区list &#xff1a;列表分区hash &#xff1a;哈希分区 一、范围分区 根据某个字段的值&#xff0c;将数据存入不同的分区表中。 创建父表 create table test_person_table (name varchar(64),ag…
阅读更多...
SpringSecurity工作原理

SpringSecurity工作原理

实现功能就是继承这几个对应功能的类。 大概工作流程 Spring Security 的过滤器&#xff08;Filters&#xff09;和拦截器&#xff08;Interceptors&#xff09;是 Spring Security 框架中用于保护 web 应用安全的重要组件。它们在处理 HTTP 请求时扮演不同的角色&#xff0c…
阅读更多...
【动态规划】LeetCode-62.不同路径

【动态规划】LeetCode-62.不同路径

&#x1f388;算法那些事专栏说明&#xff1a;这是一个记录刷题日常的专栏&#xff0c;每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目&#xff0c;在这立下Flag&#x1f6a9; &#x1f3e0;个人主页&#xff1a;Jammingpro &#x1f4d5;专栏链接&…
阅读更多...
最新文章

Copyright @ 2022~2023