[LeetCode] 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

leetcode - Find Elements in a Contaminated Binary Tree

문제 유형: 트리, 해시

문제 난이도: Medium

 

문제

Given a binary tree with the following rules:

1. root.val == 0
2. For any treeNode:
   1. If treeNode.val has a value x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
   2. If treeNode.val has a value x and treeNode.right != null, then treeNode.right.val == 2 * x + 2

Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.

Implement the FindElements class:

• FindElements(TreeNode* root) Initializes the object with a contaminated binary tree and recovers it.
• bool find(int target) Returns true if the target value exists in the recovered binary tree.

다음의 규칙으로 이진트리가 주어진다:

root.Val == 0

왼쪽자식의 값은 부모노드의 값*2+1, 오른쪽자식의 값은 부모노드의 값*2+2.

이진트리의 값이 모두 -1로 바뀌었다.

FindElements 클래스를 구현하시오:

• FindElements(TreeNode* root)는 객체를 초기화하고 복구합니다.
• bool find(int target)는 복구된 이진트리에 target이 있으면 반환합니다.

 

풀이

우리는 생성자에서 미리 테이블을 초기화해서 find는 O(1)에 찾을 수 있도록 할 것이다.

복구된 트리의 번호들이 완전이진트리의 번호 규칙과 같다는 것을 알 수 있다.

그러나 트리의 구조를 모르기에, 희소한 경우를 생각해서 해시 테이블을 이용하면 된다.

exists[target] = 가지고있는지가에 대한 정보로 하면 된다.

 

트리 복구에는 dfs, bfs둘다 가능하다. 루트에 0을 할당하고, dfs 또는 bfs로 트리를 직접 복구하지 말고, 해시테이블에 복귀된 트리의 노드번호의 존재여부를 저장한다.

find로 간단하게 찾을 수 있다.

 

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class FindElements {
private:
    unordered_set<int> exists;
    void bfs(TreeNode* root) {
        if(!root) return;
        root -> val = 0;
        queue<TreeNode*> q;
        q.push(root);
        exists.insert(0);

        while(!q.empty()) {
            auto currNode = q.front();
            q.pop();

            if(currNode -> left) {
                currNode -> left -> val = ((currNode -> val)*2)+1;
                q.push(currNode -> left);
                exists.insert(currNode -> left -> val);
            }
            if(currNode -> right) {
                currNode -> right -> val = ((currNode -> val)*2)+2;
                q.push(currNode -> right);
                exists.insert(currNode -> right -> val);
            }
        }
    }
public:
    FindElements(TreeNode* root) {
        bfs(root);
    }
    
    bool find(int target) {
        return exists.find(target) != exists.end();
    }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */

 

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type FindElements struct {
    mp map[int]bool
}


func Constructor(root *TreeNode) FindElements {
    x := FindElements{}
    x.mp = make(map[int]bool)
    x.Bfs(root)
    return x
}

func (this *FindElements) Bfs(root *TreeNode) {
    this.mp[0] = true
    root.Val = 0
    q := []*TreeNode{root}
    for len(q) > 0 {
        curr := q[0]
        q = q[1:]

        if curr.Left != nil {
            curr.Left.Val = curr.Val*2+1
            q = append(q, curr.Left)
            this.mp[curr.Left.Val] = true
        }
        if curr.Right != nil {
            curr.Right.Val = curr.Val*2+2
            q = append(q, curr.Right)
            this.mp[curr.Right.Val] = true
        }
    }
}


func (this *FindElements) Find(target int) bool {
    if _, exists := this.mp[target]; exists {
        return true
    }
    return false
}


/**
 * Your FindElements object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Find(target);
 */