找到两个二叉搜索树的交集

Question

我正在构建并返回一个新的二叉搜索树，该树由另外两个二叉搜索树的交集构成。我有一个 find 函数，我用它来检查是否在第二棵树中找到了第一棵树的任何值，如果是，我将它们插入到新树中。我的问题是新树“res”不会在递归时更新。因此，如果我用 8、4、10 对 tree1 进行测试，而 tree2 是 8、6、4、13，我的新树只包含 8 而不是 8 和 4。感谢任何反馈！

BinSearchTree *BinSearchTree::intersectWith(TreeNode *root1, TreeNode *root2) {
BinSearchTree *res = new BinSearchTree();

//traverse one tree and use find to traverse the second tree
if(local_find(root2, root1->value()) && !local_find(res->root, root1->value()))
    res->insert(root1->value());
if(root1->leftSubtree() != nullptr)
    intersectWith(root1->leftSubtree(), root2);
if(root1->rightSubtree() != nullptr)
    intersectWith(root1->rightSubtree(), root2);
return res;

}

Answer 1

每次通过调用 'new BinSearchTree()' 调用 intersectWith() 时都会覆盖 res。

要解决此问题，请在 interSectWith() 之外创建 res，然后将其作为第三个参数传入。（然后您还可以考虑使 intersectWith() return 无效，因为不再需要 return 值。）

找到两个二叉搜索树的交集

Finding the intersection of two binary search trees

c++

data-structures

binary-search-tree