【深度优先】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]为根的树的最大节点值
mValueIndex	key: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);
}
};

测试环境

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

或者操作系统：win10 开发环境：

VS2022 C++17

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

作者推荐

题目

分析

正确分析

错误分析

错误原因

解决方法

变量解释

代码

优化

分析

判断合法的根的代码

中序遍历

中序遍历优化

2023年6月旧版

测试环境

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

作者推荐

题目

分析

正确分析

错误分析

错误原因

解决方法

变量解释

代码

优化

分析

判断合法的根的代码

中序遍历

中序遍历优化

2023年6月旧版

测试环境

热门文章

最新文章

相关电子书