2个二叉树的交集会引发Stack Overflow错误

我试图交叉两个二叉树，并创建一个新的二叉树与相同的节点，但以下创建stackOverflow错误。 谁能帮我？

private OrderedSet resultIntersect = new OrderedSet(); public OrderedSet intersection(OrderedSet other) { OrderedSet result = new OrderedSet(); 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 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 resultIntersect = new OrderedSet(); public OrderedSet intersection(OrderedSet other) { OrderedSet result = new OrderedSet(); result = resultIntersect; return result; } private void intersection(OrderedSet 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); } 

Answer 1

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

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

清理那些缺陷，我得到：

 public OrderedSet intersection(OrderedSet other) { OrderedSet result = new OrderedSet(); intersection(result, root, other.root); return result; } private void intersection(OrderedSet 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); } 

我不知道这是否有效，但它更接近

Answer 2

堆栈溢出错误表明在达到堆栈限制之前没有触底的递归。 主要嫌疑人是private void intersection法。 如果输入是正确的二叉树，则应该在某个时刻达到条件(root1 == null || root2 == null) – 但对于非常大的非平衡二叉树来说这可能需要很长时间，或者从来没有“二叉树”是有缺陷的，并且在某个地方有一个循环。 这两种情况都可能是溢出的原因。

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