[코테연습] 1261. Find Elements in a Contaminated Binary Tree

https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/description/?envType=daily-question&envId=2025-02-21

 

📌 문제 타입

• Tree (트리)
• Binary Tree (이진 트리)
• Hashing (해싱)
• Depth-First Search (DFS) / Breadth-First Search (BFS)

---

🔍 문제 분석

• 문제 배경
  주어진 이진 트리는 -1로 오염되어 있음. 이 트리를 복구한 후 특정 값을 포함하는지 확인해야 함.
• 트리 복구 규칙
  1. 루트 노드는 항상 0으로 설정됨.
  2. x의 왼쪽 자식이 존재하면 값은 2*x + 1
  3. x의 오른쪽 자식이 존재하면 값은 2*x + 2
• 요구 사항
  • 복구된 트리에서 find(x)를 여러 번 호출하며, 해당 값이 존재하는지 O(1)에 가깝게 판별해야 함.

---

📝 문제 풀이

1. 트리 복구
   • DFS 또는 BFS를 활용하여 루트부터 재귀적으로 복구.
   • Set을 활용하여 모든 노드 값을 저장(빠른 탐색을 위해).
2. 값 탐색 (find)
   • Set에 해당 값이 있는지 O(1) 시간 복잡도로 탐색.
3. 구현 방식
   • TreeNode 클래스를 활용하여 트리 탐색.
   • Set을 이용해 존재 여부를 빠르게 확인.
   • DFS 또는 BFS로 트리를 복구한 후, find(x) 호출 시 set.contains(x)로 확인.

 

class FindElements {
    
    TreeNode node;
    Set<Integer> nums;

    public FindElements(TreeNode root) {
        root.val = 0;
        nums = new HashSet<>();
        nums.add(root.val);
        set(root, root.val);
        node = root;
    }

    void set(TreeNode node, int val){
        if (node.left != null) {
            node.left.val = 2 * val + 1;
            nums.add(node.left.val);
            set(node.left, node.left.val);
        }
        if (node.right != null) {
            node.right.val = 2 * val + 2;
            nums.add(node.right.val);
            set(node.right, node.right.val);
        }
    }
    
    public boolean find(int target) {
        return nums.contains(target);
    }

}