leetcode 1379(트리), 46(permutation), 98(트리), 173(트리)

1379번. https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/

 

트리 순환 문제이다. 왜 굳이 original과 cloned을 따로 나눴는지 모르겠다. pre order던 post order던 순회하면서 해당 val이 있으면 return하도록 하면 문제는 풀린다. 

 

아래는 일반적인 dfs식 트리순회.

class Solution(object):
    def getTargetCopy(self, original, cloned, target):
        stack = [cloned]
        while stack:
            pop = stack.pop()
            if pop.val == target.val:
                return pop
            
            if pop.left:
                stack.append(pop.left)
            if pop.right:
                stack.append(pop.right)

근데 아래의 해답에서 신선한 트리 순회 방법을 발견했다.(지금 보니 python3버전만 됨.)

 

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/discuss/537686/Python-Clean-and-Pythonic-way-using-iterator(generator)-solving-followup-too

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        def it(node):
            if node:
                yield node
                yield from it(node.left)
                yield from it(node.right)
                
        for n1, n2 in zip(it(original), it(cloned)):
            if n1 == target:
                return n2

이렇게 만들면 yield로 자연스럽게 root, left, right을 yield로 반환하는데 아래의 for문에서 original과 cloned를 묶어서 순환함으로써 original의 target위치가 나오면 cloned의 레퍼런스를 반환한다.yield를 이용한 트리 순회.. 알아뒀다 써먹어야겠다. 

 

 

46번. https://leetcode.com/problems/permutations/submissions/

 

permutation을 구현하는 문제이다. 파이썬에는 permutations라이브러리가 있지만 그걸 사용하면 알고리즘 문제를 푸는 의미가 없다. 알고리즘 공부를 한지 하도 오래되어서 어떻게 접근할지 모르겠다가, 해답에서 dfs를 사용한 방법을 보고 아이디어를 얻어서 직접 짰다.

class Solution(object):
    def permute(self, nums):
        visited = set()
        stack = []
        for i in xrange(len(nums)):
            stack.append([ [nums[i]], nums[i+1:] + nums[:i] ])

        while stack:
            cur_path, future_path = stack.pop()
            if not future_path:
                visited.add(tuple(map(int, cur_path)))
                continue

            for i in xrange(len(future_path)):
                if tuple(map(int, cur_path + [future_path[i]])) in visited:
                    continue
                stack.append([ cur_path + [future_path[i]], future_path[i+1:] + future_path[:i] ])
        return map(list, visited)

98번. https://leetcode.com/problems/validate-binary-search-tree/

 

트리를 검증하는 문제이다. 왼쪽 자식은 루트보다 작아야 한다. 오른쪽 자식은 루트보다 커야 한다.

inorder로 정렬 후 왼쪽 자식이 오른쪽 자식보다 크거나 같은지만 체크하면 된다.

class Solution(object):
    def isValidBST(self, root):
        tree = []
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            tree.append(node.val)
            inorder(node.right)
        inorder(root)
        
        for i in xrange(len(tree)-1):
            if tree[i] >= tree[i+1]:
                return False
        return True

173번. https://leetcode.com/problems/binary-search-tree-iterator/

 

바로 위에 98번이랑 동일하다.. inorder로 정렬후 로직에 맞게 리턴하면 된다.

class BSTIterator(object):

    def __init__(self, root):
        self.tree = []
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            self.tree.append(node.val)
            inorder(node.right)
        inorder(root)

    def next(self):
        return self.tree.pop(0)

    def hasNext(self):
        return True if len(self.tree) > 0 else False