leetcode 863(트리), 430(linked list, stack), 114, 211(구현, 정규식)

863 https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

1. 그래프 개념으로 어떤 한 노드에 연결된 모든 노드를 찾는다. 연결된 노드는 [부모, 왼쪽 자식, 오른쪽 자식]이다. 이것들을 node_list에 저장해놓는다.

2. 저장한 후에는 target을 시작점으로 [부모, 왼쪽 자식, 오른쪽 자식]을 돌면서 거리가 K인 노드들을 dfs로 탐색한다.

from collections import deque

class Solution(object):
    def distanceK(self, root, target, K):
        node_list = {}
        queue = deque([[root, None]])  # node, parent
        while queue:
            node, parent = queue.popleft()
            if node and node not in node_list:
                node_list[node] = [parent, node.left, node.right]  # 갈수있는 노드들의 정보들을 여기에 저장
                queue.append([node.left, node])
                queue.append([node.right, node])
        
        stack = deque([[target, 0]])
        visited = set([target.val])
        ret = []
        while stack:
            node, distance = stack.pop()
            if distance == K:
                ret.append(node.val)
                continue
            for _next in node_list[node]:
                if _next and _next.val not in visited:
                    stack.append([_next, distance + 1])
                    visited.add(_next.val)
                    
        return ret

430 https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

스택으로 가져온다. next를 먼저 가져오고 child를 가져오면 child안에 next나 child가 또 있을 경우 그것들부터 처리하게 된다. 다 가져온 후 서로 이어준다.

from collections import deque

class Solution(object):
    def flatten(self, head):
        if not head:
            return head
        
        node_list = []
        stack = deque([head])
        
        while stack:
            node = stack.pop()
            node_list.append(node)
            if node.next:
                stack.append(node.next)
            if node.child:
                stack.append(node.child)
        
        ret = node_list.pop(0)
        while node_list:
            n = node_list.pop(0)
            head.next = n
            head.child = None
            n.prev = head
            head = n
        
        return ret

114 https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

바로 위의 430이랑 똑같아서 설명이 필요 없다.

from collections import deque

class Solution(object):
    def flatten(self, root):
        if not root:
            return root
        
        node_list = []
        stack = deque([root])
        while stack:
            node = stack.pop()
            node_list.append(node)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
                
        ret = head = node_list.pop(0)
        while node_list:
            n = node_list.pop(0)
            head.right = n
            head.left = None
            head = n
         
        return ret

211 https://leetcode.com/problems/add-and-search-word-data-structure-design/

시키는대로 구현한다. 길이별 dictionary를 만들어놓고 해당하는것만 가져와서 검사한

class WordDictionary(object):

    def __init__(self):
        self.str_dict = {}

    def addWord(self, word):
        _len = len(word)
        self.str_dict[_len] = self.str_dict.get(_len, []) + [word]

    def search(self, word):
        _len = len(word)
        if _len not in self.str_dict:
            return False
        
        for wordlist in self.str_dict[_len]:
            flag = True
            for i in xrange(len(word)):
                if word[i] != wordlist[i] and word[i] != ".":
                    flag = False
            if flag:
                return True
        return False

정규식으로도 느리지만 되긴 된다.

import re

class WordDictionary(object):

    def __init__(self):
        self.str = '\n'
        
    def addWord(self, word):
        self.str += '{}\n'.format(word)

    def search(self, word):
        self.regex = re.compile('\n'+word+'\n')
        return True if re.search(self.regex, self.str) else False

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)