목록dfs (1)

Tech for good

[Leetcode/Hash Set] 653. Two Sum IV - Input is a BST

해시셋(Hash Set) 활용 -중복을 방지하면서 각 노드를 탐색할 때 (k - 현재 노드 값)이 존재하는지 확인하는 방법. 설명dfs 함수를 사용하여 트리를 깊이 우선 탐색(DFS) 한다.각 노드를 방문할 때 k - node.val이 seen 집합에 존재하는지 확인한다.존재하면 True를 반환하고, 없으면 현재 노드 값을 seen에 추가한 후 왼쪽과 오른쪽 서브트리를 탐색한다.전체 탐색이 끝날 때까지 조건을 만족하는 쌍이 없으면 False를 반환한다.시간 복잡도각 노드를 한 번씩 방문하므로 O(N) (N은 트리의 노드 개수).공간 복잡도최악의 경우 모든 노드 값을 seen에 저장해야 하므로 O(N). # Definition for a binary tree node.class TreeNode: de..
IT/Computer Science 2025. 2. 15. 00:53
이전 Prev 1 Next 다음