값 0, 1 및 2를 포함하는 이진 트리가 있다고 가정합니다. 루트에는 최소한 하나의 0 노드와 하나의 1 노드가 있습니다. 이제 트리에서 가장자리를 삭제하고 트리가 두 개의 다른 트리가 되는 작업이 있다고 가정합니다. 우리는 두 트리 중 어느 것도 0 노드와 1 노드를 모두 포함하지 않도록 한 가장자리를 삭제할 수 있는 방법의 수를 찾아야 합니다.
따라서 입력이 다음과 같으면
0에서 2까지의 가장자리만 삭제할 수 있으므로 출력은 1이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 카운트 :=[0, 0, 0]
- dfs() 함수를 정의합니다. 노드가 필요합니다.
- 노드가 null이 아니면
- 사전 :=카운트
- dfs(노드 왼쪽)
- dfs(노드 오른쪽)
- count[노드 값] :=count[노드 값] + 1
- node.count :=i에 대한 (count[i] - pre[i])의 목록은 0과 1입니다.
- dfs2() 함수를 정의합니다. 이것은 노드가 필요합니다.
- 노드가 null이 아니면
- par이 null이 아니면
- (a0, a1) :=노드 수
- (b0, b1) :=(count[0] - a0, count[1] - a1)
- (a0이 0과 같거나 a1이 0과 같은 경우) 및 (b0이 0과 같거나 b1이 0과 같은 경우)
- ans :=ans + 1
- dfs2(노드의 왼쪽, 노드)
- dfs2(노드 오른쪽, 노드)
- par이 null이 아니면
- 기본 방법에서 다음을 수행합니다. -
- dfs(루트)
- ans :=0
- dfs2(루트)
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
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): count = [0, 0, 0] def dfs(node): if node: pre = count[:] dfs(node.left) dfs(node.right) count[node.val] += 1 node.count = [count[i] - pre[i] for i in range(2)] dfs(root) def dfs2(node, par=None): if node: if par is not None: a0, a1 = node.count b0, b1 = count[0] - a0, count[1] - a1 if (a0 == 0 or a1 == 0) and (b0 == 0 or b1 == 0): self.ans += 1 dfs2(node.left, node) dfs2(node.right, node) self.ans = 0 dfs2(root) return self.ans ob = Solution() root = TreeNode(0) root.left = TreeNode(0) root.right = TreeNode(2) root.right.left = TreeNode(1) root.right.right = TreeNode(1) print(ob.solve(root))
입력
root = TreeNode(0) root.left = TreeNode(0) root.right = TreeNode(2) root.right.left = TreeNode(1) root.right.right = TreeNode(1)
출력
1