두 개의 이진 트리가 있다고 가정하고 구조와 값이 정확히 동일한지 여부를 확인해야 합니다. 쌍둥이 나무라고 할 수 있습니다.
따라서 입력이 다음과 같으면
그러면 출력은 첫 번째 쌍에 대해 True, 두 번째 쌍에 대해 false, 세 번째 쌍에 대해 두 번째 및 세 번째 항목이 다르고 구조가 각각 다르기 때문에 출력됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
solve() 메서드를 정의하면 두 개의 루트가 필요합니다.
-
root0이 null이고 root1이 null이면
-
참을 반환
-
-
root0이 null이거나 root1이 null이면
-
거짓을 반환
-
-
root0의 값이 root1의 값과 같지 않으면
-
거짓을 반환
-
-
solve(root0의 왼쪽, root1의 왼쪽) 및 solve(root0의 오른쪽, root1의 오른쪽)가 true이면 true를 반환하고 그렇지 않으면 false를 반환합니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def solve(self, root0, root1): if not root0 and not root1: return True if not root0 or not root1: return False if root0.val != root1.val: return False return self.solve(root0.left, root1.left) and self.solve(root0.right, root1.right) ob = Solution() root1 = TreeNode(10) root1.left = TreeNode(5) root1.right = TreeNode(15) root1.left.left = TreeNode(3) root1.left.right = TreeNode(8) root2 = TreeNode(10) root2.left = TreeNode(5) root2.right = TreeNode(15) root2.left.left = TreeNode(3) root2.left.right = TreeNode(8) print(ob.solve(root1, root2))
입력
root1 = TreeNode(10) root1.left = TreeNode(5) root1.right = TreeNode(15) root1.left.left = TreeNode(3) root1.left.right = TreeNode(8) root2 = TreeNode(10) root2.left = TreeNode(5) root2.right = TreeNode(15) root2.left.left = TreeNode(3) root2.left.right = TreeNode(8)
출력
True