두 개의 이진 트리가 제공된다고 가정합니다. 이진 트리의 각 수준이 다른 이진 트리의 동일한 수준의 아나그램인지 확인해야 합니다. 아나그램이면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
따라서 입력이 다음과 같으면
, 출력은 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- tree_1은 첫 번째 트리의 루트 노드이고 tree_2는 두 번째 트리의 루트 노드입니다.
- tree_1이 null과 같고 tree_2가 null과 같으면
- 참 반환
- tree_1이 null과 같거나 tree_2가 null과 같으면
- 거짓을 반환
- queue1 :=새 대기열
- queue2 :=새 대기열
- queue1 끝에 tree_1 삽입
- queue2 끝에 tree_2 삽입
- 1이 0이 아닌 동안 do
- size1 :=queue1의 크기
- size2 :=queue2의 크기
- size1이 size2와 같지 않으면
- 거짓을 반환
- size1이 0과 같으면
- 루프에서 나오다
- curr_level1 :=새 목록
- curr_level2 :=새 목록
- size1> 0일 때 수행
- node1 :=queue1의 첫 번째 요소
- queue1에서 첫 번째 요소 삭제
- node1의 왼쪽이 null과 같지 않으면
- queue1 끝에 node1 왼쪽 삽입
- node1의 오른쪽이 null과 같지 않으면
- queue1 끝에 node1 오른쪽 삽입
- 크기1 :=크기1 - 1
- node2 :=queue2의 첫 번째 요소
- queue2에서 첫 번째 요소 삭제
- node2의 왼쪽이 null과 같지 않으면
- queue2의 끝에 node2의 왼쪽 삽입
- node2의 오른쪽이 null과 같지 않으면
- queue2의 끝에 node2의 오른쪽 삽입
- curr_level1 끝에 node1 값 삽입
- curr_level2 끝에 node2 값 삽입
- curr_level1 목록 정렬
- curr_level2 목록 정렬
- curr_level1이 curr_level2와 같지 않으면
- 거짓을 반환
- 참 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def make_tree(elements): tree = tree_node(elements[0]) for element in elements[1:]: insert_value(tree, element) return tree def insert_value(temp,value): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if value is not None: temp.left = tree_node(value) else: temp.left = tree_node(0) break else: que.append(temp.left) if (not temp.right): if value is not None: temp.right = tree_node(value) else: temp.right = tree_node(0) break else: que.append(temp.right) class tree_node: def __init__(self, value): self.value = value self.left = None self.right = None def solve(tree_1, tree_2) : if (tree_1 == None and tree_2 == None) : return True if (tree_1 == None or tree_2 == None) : return False queue1 = [] queue2 = [] queue1.append(tree_1) queue2.append(tree_2) while (1) : size1 = len(queue1) size2 = len(queue2) if (size1 != size2): return False if (size1 == 0): break curr_level1 = [] curr_level2 = [] while (size1 > 0): node1 = queue1[0] queue1.pop(0) if (node1.left != None) : queue1.append(node1.left) if (node1.right != None) : queue1.append(node1.right) size1 -= 1 node2 = queue2[0] queue2.pop(0) if (node2.left != None) : queue2.append(node2.left) if (node2.right != None) : queue2.append(node2.right) curr_level1.append(node1.value) curr_level2.append(node2.value) curr_level1.sort() curr_level2.sort() if (curr_level1 != curr_level2) : return False return True tree_1 = make_tree([5, 6, 7, 9, 8]) tree_2 = make_tree([5, 7, 6, 8, 9]) print(solve(tree_1, tree_2))
입력
[5, 6, 7, 9, 8], [5, 7, 6, 8, 9]
출력
True