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

news/2024/7/20 20:01:51 标签: 深度优先, 算法, c++, LeetCode, 二叉搜索树, 合并, 森林

作者推荐

动态规划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.niftyadmin.cn/n/5233251.html

相关文章

windows系统bat脚本命令总结之删除命令（del）

windows系统bat脚本命令总结之删除命令（del）

前言 做了一段时间的bat脚本开发&#xff0c;bat脚本中有各种各样的命令跟传统的编程逻辑完全不同&#xff0c;本专栏会讲解下各种各式的命令使用方法。 本篇文章讲解的是windows系统的删除命令"del"。 del命令 在Windows系统下&#xff0c;可以使用del命令来删除文…
阅读更多...
zookeeper 单机伪集群搭建简单记录（实操课程系列）

zookeeper 单机伪集群搭建简单记录（实操课程系列）

本系列是zookeeper相关的实操课程&#xff0c;课程测试环环相扣&#xff0c;请按照顺序阅读测试来学习zookeeper 1、官方下载加压后&#xff0c;根目录下新建data和log目录&#xff0c;然后分别拷贝两份&#xff0c;分别放到D盘&#xff0c;E盘&#xff0c;F盘 2、data目录下面…
阅读更多...
【哈希】1.两数之和

【哈希】1.两数之和

题目&#xff1a;https://leetcode.cn/problems/two-sum/description/?envTypestudy-plan-v2&envIdtop-100-liked class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map new HashMap<>();for (int i 0; i < nums.l…
阅读更多...
深度学习常见回归分支算法逐步分析，各种回归之间的优缺点，适用场景，举例演示

深度学习常见回归分支算法逐步分析，各种回归之间的优缺点，适用场景，举例演示

文章目录 1、线性回归&#xff08;Linear Regression&#xff09;1.1 优点1.2 缺点1.3 适用场景1.4 图例说明 2、多项式回归&#xff08;Polynomial Regression&#xff09;2.1 优点2.2 缺点2.3 适用场景2.4 图例说明 3、决策树回归&#xff08;Decision Tree Regression&#…
阅读更多...
Python自动化——原生警告框和自定义弹窗的区别

Python自动化——原生警告框和自定义弹窗的区别

原生警告框&#xff08;Native Alert&#xff09;和自定义弹窗在实现方式和特性上有一些区别&#xff1a; 实现方式&#xff1a; 原生警告框&#xff1a;由浏览器原生提供的警告框&#xff0c;通常是通过 JavaScript 中的 alert()、confirm()、prompt() 等方法触发的&#xff0…
阅读更多...
QProcess 启动 进程 传参数 启动控制台进程 传参

QProcess 启动 进程 传参数 启动控制台进程 传参

目录 QProcess 启动外部程序的两种方式 依赖式 分离式&#xff1a; 启动进程前的预处理 设置启动路径 设置启动命令参数 设置启动工作目录 设置启动所需环境&#xff1a; 启动的状态 code smple: QProcess 控制台进程 QProcess启动控制台不显示窗口 注意&#xff1a;…
阅读更多...
P8A009-A011活动目录安全

P8A009-A011活动目录安全

设置目录数据库访问权限 【预备知识】 活动目录&#xff08;Active Directory&#xff09;是面向Windows Standard Server、Windows Enterprise Server以及 Windows Datacenter Server的目录服务。&#xff08;Active Directory不能运行在Windows Web Server上&#xff0c;但…
阅读更多...
python数据类型List分析

python数据类型List分析

1. 创建列表 在 python 中, [] 表示一个列表 a [] print(type(a)) #<class list>a list() print(type(a)) #<class list>b [ 1, 2, 3, 4] print(type(b)) #<class list>c [1, 2, 3, hello] print(type(c)) #<class list>print(c…
阅读更多...
最新文章

Copyright @ 2022~2023