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. 두 번째 리턴은 널 (null) 테스트 전에 뿌리를 역 참조
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() 기반 비교가 더 적절할 것입니다.