二叉搜索树交集计算递归实现结果树不更新问题求解

数据老陈

2026-10-1

核心问题

你每次递归调用intersectWith时都会新建一个独立的BinSearchTree对象res，处理左右子树时找到的交集元素都插入到了子调用的临时res中，这些临时对象没有和顶层返回的res关联，调用结束后直接内存泄漏，没有任何作用。
最终只有顶层调用（处理root1根节点，即测试用例中的8）的res会被返回，所以结果只包含8。

修复方案

建议单独拆分递归遍历逻辑，把用于存储结果的公共树作为参数传递，避免每次递归重复创建结果树，示例修改代码如下：

// 新增私有辅助函数，用于递归遍历root1，把交集元素插入到公共的res树中
void BinSearchTree::traverseAndCollect(TreeNode *root1, TreeNode *root2, BinSearchTree *res) {
    // 边界判断：当前节点为空直接返回
    if (root1 == nullptr) {
        return;
    }
    // 检查当前值是否是交集，是就插入结果树
    if(local_find(root2, root1->value()) && !local_find(res->root, root1->value())) {
        res->insert(root1->value());
    }
    // 递归遍历左右子树，共用同一个res
    traverseAndCollect(root1->leftSubtree(), root2, res);
    traverseAndCollect(root1->rightSubtree(), root2, res);
}

// 原对外接口只做初始化和结果返回
BinSearchTree *BinSearchTree::intersectWith(TreeNode *root1, TreeNode *root2) {
    BinSearchTree *res = new BinSearchTree();
    traverseAndCollect(root1, root2, res);
    return res;
}