이미지 데이터 구조

Question

이미지 (정사각형 이미지)는 트리로 저장할 수 있습니다. 이미지가 흰색이면 노드가 흰색이고 이미지가 검은 색이면 검은 색이며 이미지가 모두 포함되어 있으면 혼합됩니다. 흰색 노드와 검은 색 노드는 나뭇잎이며, 혼합 노드는 이미지에서 4 사분면을 나타내는 정확히 4 개의 자식을 갖습니다. 주어진 2 개의 이미지 (나무), 그들의 교차점을 나타내는 이미지를 찾으십시오. (교차로 : B^B -> B, B^W -> W, W^W -> W) 이것은 Google 인터뷰 질문입니다

Answer 1

둘 다 이진 트리로 표시되므로 트리 구조를 탐색해야합니다 루트에서 시작하여 언제든지 두 트리의 노드 색상을 확인하고 다른 트리에 결과를 저장합니다. 둘 중 하나라도 검은 색이나 흰색이면 더 이상 횡단을 멈 춥니 다. 그렇지 않으면 그 중 하나가 둘 다 단일 색상으로 발견 될 때까지 그 노드에서 추가로 횡단합니다.

Answer 2

다음과 같은 간단한 방법이 있습니다. 동일한 순서를 사용하여 두 트리를 동시에 트래버스합니다. 그렇게하는 동안 출력 트리를 빌드하십시오. 그런 다음 : 당신은 두 나무의 혼합 노드, 출력 혼합 노드를 참조하면

1. 는
2. 하나 나무에 혼합 노드, 그러나 다른 출력 흰색 노드에 흰색 노드를 참조 (그리고 경우 무시 순회의 혼합 노드)
3. 하나의 트리에는 혼합 노드가 있지만 다른 노드에는 검정 노드가있는 경우 혼합 노드와 그 자식을 출력 트리에 복사하십시오.
4. 두 개의 흰색 노드가 표시되면 출력 흰색 노드
5. 두 개의 검정 노드가 표시되면 검은 노드를 출력하십시오.

실제로는 흰색 자식 만있는 혼합 노드를 만들 수 있으므로 흰색 자식 만있는 혼합 노드를 축소하는 트리를 가로 지르는 압축 단계가 필요할 수 있습니다.

편집 : 출력 검정 노드가 아래에 있는지 여부를 재귀에 알리는 것으로 압축 단계를 피할 수 있다고 생각합니다. 대답이 '아니오'인 경우 흰색 잎을 넣습니다.