1261-kir3i.md

1261. Find Elements in a Contaminated Binary Tree

Solution

• 시간복잡도

  setVal: O(N), N은 트리에 매달린 노드의 수

  find: O(1)

• 알고리즘

  구현, 트리

• 풀이설명

  1. 트리에 값을 세팅해주는 건 주어진 binary tree를 순회하면서 자리에 맞는 값을 넣어주면 됩니다. setVal이라는 이름의 재귀함수로 구현했습니다.
  2. setVal에서 값을 넣을 때 Set에 추가하는 과정을 넣으면 나중에 find에서 찾기 용이합니다. 이 때 HashSet을 이용해서 find의 시간복잡도가 O(1)이 되도록 했습니다.

• 소스코드

  • C++

    class FindElements {
    public:
        unordered_set<int> s;
        FindElements(TreeNode* root) {
            setVal(root, 0);
        }
        
        void setVal(TreeNode *node, const int &val) {
            if(!node)   return;
            node->val = val;
            s.insert(val);
            setVal(node->left, 2*val+1);
            setVal(node->right, 2*val+2);
        }
        
        bool find(int target) {
            return s.find(target) != s.end();
        }
    };

  • Python

    class FindElements:
        
        def __init__(self, root):
            self.s = set([])
            self.setVal(root, 0)
        def setVal(self, node, val):
            if not node:
                return
            node.val = val
            self.s.add(val)
            self.setVal(node.left, 2*val+1)
            self.setVal(node.right, 2*val+2)
    
        def find(self, target):
            if target in self.s:
                return True
            else:
                return False

  • Java

    class FindElements {
        
        public Set<Integer> s = new HashSet<Integer>();
        public FindElements(TreeNode root) {
            setVal(root, 0);
        }
        
        public void setVal(TreeNode node, int val) {
            if(node == null)    return;
            node.val = val;
            s.add(val);
            this.setVal(node.left, 2*val+1);
            this.setVal(node.right, 2*val+2);
        }
        
        public boolean find(int target) {
            return s.contains(target);
        }
    }