2個二叉樹的交集拋出堆棧溢出錯誤

Question

我想交叉兩個二叉樹，並創建一個新的二叉樹與相同的節點，但以下創建一個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); 
} 

Answer 1

我不知道具體的問題，但有一些問題。

1. 爲什麼「其他」傳遞到第二個交點（它從來沒有使用過）？
2. 在插入集合後不應該返回嗎？
3. 你不應該傳入本地OrderedSet（稱爲result）並插入它，而不是全局變量？
4. 您不應該比較root1和root2的數據，而不是節點本身？
5. 第二回是多餘的
6. 取消引用您測試空前根
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); 
} 

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

Answer 2

堆棧溢出錯誤表明在到達堆棧限制之前沒有達到最低限度的遞歸。主要嫌犯是private void intersection方法。如果輸入是正確的二叉樹，那麼應該在某個時間點達到(root1 == null || root2 == null)的條件 - 但是對於非常大的不平衡二叉樹可能需要很長時間，或者如果「二叉樹」有缺陷並且有循環某處。兩種情況都可能是溢出的原因。

我也想指出的是，在相同的方法條件if (root1 == root2)很可能沒有做它的目的是：參數root1和root2很可能不是同一個對象，這樣的條件幾乎肯定是假的。其他一些基於equals()的比較可能更合適。