0

我正在尝试使两棵二叉树相交，并使用相同的节点创建一棵新的二叉树，但以下会产生 stackOverflow 错误。谁能帮我？

private OrderedSet<E> resultIntersect = new OrderedSet<E>();

public OrderedSet<E> intersection(OrderedSet<E> other) {
    OrderedSet<E> result = new OrderedSet<E>();
    if (other.root == null || root == null)
        return result;
    else if (height() == 0 && other.height() == 0
            && other.root.data.equals(root.data)) {
        result.insert(root.data);
        return result;
    } else {
        intersection(other, root, other.root);
        result = resultIntersect;
    }
    return result;
}

private void intersection(OrderedSet<E> other, TreeNode root1,
        TreeNode root2) {
    if (root1 == root2) {
        resultIntersect.insert(root1.data);
    }
    if (root1 == null || root2 == null) {
        return;
    }
    intersection(other, root1.left, root2.left);
    intersection(other, root1.right, root2.right);
}

编辑

我觉得这更接近我需要的方式，但我仍然得到错误。

private OrderedSet<E> resultIntersect = new OrderedSet<E>();

public OrderedSet<E> intersection(OrderedSet<E> other) {
    OrderedSet<E> result = new OrderedSet<E>();
    result = resultIntersect;
    return result;
}

private void intersection(OrderedSet<E> other, TreeNode t) {
    if (other.contains(t.data)) {
        resultIntersect.insert(t.data);
    }
    if(t.left != null)
        intersection(other, t.left);
    if(t.right != null)
        intersection(other, t.right);
}
4

2 回答 2

1

我不知道具体问题，但有一些问题。

  1. 为什么将“其他”传递到第二个路口（从未使用过）？
  2. 插入集合后不应该返回吗？
  3. 您不应该传入本地 OrderedSet （称为result）并插入其中，而不是全局变量吗？
  4. 您不应该比较 root1 和 root2 的数据而不是节点本身吗？
  5. 第二次回报是多余的
  6. 在测试 null之前取消引用根
  7. 初始测试是不必要的

清理这些缺陷，我得到：

public OrderedSet<E> intersection(OrderedSet<E> other) {
    OrderedSet<E> result = new OrderedSet<E>();
    intersection(result, root, other.root);
    return result;
}

private void intersection(OrderedSet<E> result, TreeNode root1,
        TreeNode root2) {
    if (root1 == null || root2 == null) {
        return;
    }
    if (root1.data == root2.data) {
        result.insert(root1.data);
    }
    intersection(result, root1.left, root2.left);
    intersection(result, root1.right, root2.right);
}

我不知道这是否可行，但它更接近

于 2012-06-30T03:59:01.633 回答
0

堆栈溢出错误表明在达到堆栈限制之前存在没有触底的递归。主要嫌疑人是private void intersection方法。如果输入是正确的二叉树，那么(root1 == null || root2 == null)应该在某个时候达到条件——但是对于一个非常大的、不平衡的二叉树来说，这可能需要很长时间，或者如果“二叉树”有问题并且在某处有一个循环，则永远不会. 任何一种情况都可能是溢出的原因。

我还要指出，if (root1 == root2)同一方法中的条件可能没有达到预期的效果：参数root1和root2可能不是同一个对象，因此该条件几乎肯定是错误的。其他一些equals()基于比较可能更合适。

于 2012-06-30T04:00:11.620 回答