두 개의 트리가 있다고 가정하고 노드의 왼쪽 및 오른쪽 하위 트리를 여러 번 교체하여 첫 번째 트리를 두 번째 트리로 변환할 수 있는지 확인해야 합니다.
따라서 입력이 다음과 같으면
그러면 출력은 True
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
que1 :=처음에 root0인 큐
-
que2 :=처음에 root1이 있는 대기열
-
que1 및 que2가 비어 있지 않은 동안 수행
-
temp1 :=새 목록, temp2 :=새 목록
-
values1 :=새 목록, values2 :=새 목록
-
que1과 que2가 서로 다른 수의 요소를 포함하는 경우
-
거짓을 반환
-
-
범위 0에서 que1 − 1까지의 크기에 대해 다음을 수행합니다.
-
values1의 끝에 que1[i]의 값 삽입
-
values2의 끝에 que2[i]의 값 삽입
-
que1[i]의 오른쪽이 null이 아니면
-
temp1의 끝에 que1[i]의 오른쪽 삽입
-
-
que1[i]의 왼쪽이 null이 아니면
-
temp1의 끝에 que1[i]의 왼쪽 삽입
-
-
que2[i]의 오른쪽이 null이 아니면
-
temp2의 끝에 que2[i]의 오른쪽 삽입
-
-
que2[i]의 왼쪽이 null이 아니면
-
temp2의 끝에 que2[i]의 왼쪽 삽입
-
-
-
values1이 values2와 같지 않으면
-
values1이 values2와 역순으로 같지 않으면
-
거짓을 반환
-
-
-
que1 :=temp1, que2 :=temp2
-
-
참을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right class Solution: def solve(self, root0, root1): que1 = [root0] que2 = [root1] while que1 and que2: temp1 = [] temp2 = [] values1 = [] values2 = [] if len(que1) != len(que2): return False for i in range(len(que1)): values1.append(que1[i].val) values2.append(que2[i].val) if que1[i].right: temp1.append(que1[i].right) if que1[i].left: temp1.append(que1[i].left) if que2[i].right: temp2.append(que2[i].right) if que2[i].left: temp2.append(que2[i].left) if values1 != values2: if values1 != values2[::-1]: return False que1 = temp1 que2 = temp2 return True ob = Solution() root = TreeNode(2) root.right = TreeNode(4) root.right.left = TreeNode(3) root.right.right = TreeNode(5) root1 = TreeNode(2) root1.left = TreeNode(4) root1.left.left = TreeNode(3) root1.left.right = TreeNode(5) print(ob.solve(root, root1))
입력
root = TreeNode(2) root.right = TreeNode(4) root.right.left = TreeNode(3) root.right.right = TreeNode(5) root1 = TreeNode(2) root1.left = TreeNode(4) root1.left.left = TreeNode(3) root1.left.right = TreeNode(5)
출력
True