두 개의 이진 트리가 있다고 가정합니다. 두 번째 트리가 첫 번째 트리의 하위 트리인지 확인해야 합니다.
따라서 입력이 다음과 같으면
그러면 출력이 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
solve() 함수를 정의합니다. 이것은 뿌리를 내릴 것입니다, 대상
-
root가 null이고 target도 null이면
-
참을 반환
-
-
root가 null이거나 target이 null이면
-
거짓을 반환
-
-
root의 값이 target의 값과 같으면
-
해결(루트의 왼쪽, 대상의 왼쪽) 및 해결(루트의 오른쪽, 대상의 오른쪽)을 반환합니다.
-
-
그렇지 않으면
-
해결(루트의 왼쪽, 대상) 또는 해결(루트, 대상의 오른쪽)을 반환
-
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right class Solution: def solve(self, root, target): if root == None and target == None: return True if root == None or target == None: return False if root.val == target.val: return self.solve(root.left, target.left) and self.solve(root.right, target.right) else: return self.solve(root.left, target) or self.solve(root.right, target) ob = Solution() root1 = TreeNode(6) root1.left = TreeNode(4) root1.right = TreeNode(10) root1.left.left = TreeNode(3) root1.left.right = TreeNode(5) root2 = TreeNode(4) root2.left = TreeNode(3) root2.right = TreeNode(5) print(ob.solve(root1, root2))
입력
root1 = TreeNode(6) root1.left = TreeNode(4) root1.right = TreeNode(10) root1.left.left = TreeNode(3) root1.left.right = TreeNode(5) root2 = TreeNode(4) root2.left = TreeNode(3) root2.right = TreeNode(5)
출력
True