고유한 값을 포함하는 이진 트리가 있고 또 다른 값 k가 있다고 가정하면 트리에서 k-길이 고유 경로의 수를 찾아야 합니다. 경로는 부모에서 자식으로 또는 자식에서 부모로 갈 수 있습니다. 어떤 노드가 한 경로에는 나타나지만 다른 경로에는 나타나지 않는 경우 두 경로를 서로 다른 것으로 간주합니다.
따라서 입력이 다음과 같으면
k =3이면 경로가 [12,8,3], [12,8,10], [8,12,15], [3,8,10]이므로 출력은 4가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따르겠습니다-
-
dfs() 함수를 정의합니다. 노드가 필요합니다.
-
노드가 null이면
-
0이 1이고 k-1인 목록을 반환합니다.
-
-
왼쪽 :=dfs(노드의 왼쪽)
-
right :=dfs(노드의 오른쪽)
-
범위 0에서 K에 있는 i에 대해 수행
-
ans :=ans + 왼쪽[i] * 오른쪽[K - 1 - i]
-
-
res :=0의 K 크기 목록
-
해상도[0] :=1, 해상도[1] :=1
-
범위 1에서 K - 1에 있는 i에 대해 수행
-
res[i + 1] :=res[i + 1] + 왼쪽[i]
-
res[i + 1] :=res[i + 1] + 오른쪽[i]
-
-
반환 해상도
-
-
기본 방법에서 다음을 수행하십시오-
-
답변 :=0
-
-
dfs(루트)
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right class Solution: def solve(self, root, K): def dfs(node): if not node: return [1] + [0] * (K-1) left = dfs(node.left) right = dfs(node.right) for i in range(K): self.ans += left[i] * right[K - 1 - i] res = [0] * K res[0] = res[1] = 1 for i in range(1, K - 1): res[i + 1] += left[i] res[i + 1] += right[i] return res self.ans = 0 dfs(root) return self.ans ob = Solution() root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10) print(ob.solve(root, 3))
입력
root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10) 3
출력
4