leetcode 437(트리, prefix sum), 113(트리), 82(linked list), 83(linked list)

437 https://leetcode.com/problems/path-sum-iii/

1. 노드가 많아봐야 1000개라고 문제에 써있었으니 다른 방법이 기억 안날땐 O(n^2)으로 풀어도 된다.(제출 안하는것보다는 나으니.)

from collections import deque

class Solution(object):
    def pathSum(self, root, sum):
        if not root:
            return 0
        nodelist = deque([root])  # nodelist에는 모든 노드들을 저장해놓는다.
        q = deque([root])
        while q:
            p = q.popleft()
            if p.left:
                nodelist.append(p.left)
                q.append(p.left)
            if p.right:
                nodelist.append(p.right)
                q.append(p.right)
                
        ret = 0
        while nodelist:  # 모든 노드들을 돌면서 하나하나 해당되는 합이 있는지 찾는다.
            n = nodelist.popleft()
            q = deque([[n, n.val]])
            while q:
                p, temp_sum = q.popleft()
                if temp_sum == sum:
                    ret += 1
                if p.left:
                    q.append([p.left, temp_sum + p.left.val])
                if p.right:
                    q.append([p.right, temp_sum + p.right.val])
        return ret

2. 근데 O(n^2)은 느리고.. prefix sum으로 O(n)안에 풀수 있다. 내가 알던 일반적인 prefix sum하고 조금 달라서 이해하는데 시간이 걸렸다. 

https://leetcode.com/problems/path-sum-iii/discuss/141424/Python-step-by-step-walk-through.-Easy-to-understand.-Two-solutions-comparison.-%3A-)

from collections import deque

class Solution(object):
    def pathSum(self, root, target):
        if not root:
            return 0
        
        result = 0
        cache = {0: 1}
        stack = deque([[root, 0, cache]])  # 탐색할 노드, 현재까지의 합, 현재까지 방문한 리스트.
        while stack:  # dfs로 돌면서
            node, currPathSum, cache = stack.pop()
            currPathSum += node.val  # 현재까지의 합은 계속 누적해준다.
            oldPathSum = currPathSum - target  
            # oldPathSum은 현재까지의 누적합에서 target을 빼준다. cache에 현재까지 방문한 리스트가 있으므로 만약 이 oldPathSum이 cache에 존재하면 그만큼 더해준다.
            # 현재까지의 모든 합에서 target을 뺄 경우 그 차액만큼의 값이 만약 이전에 방문했던적이 있으면(cache에 있으면) target을 만들수 있다는 뜻이므로 그만큼을 cache에서 가져와서 더해준다.
            result += cache.get(oldPathSum, 0)
            cache[currPathSum] = cache.get(currPathSum, 0) + 1  # cache에는 현재까지 방문했던 경로들을 저장해준다.
            if node.left:
                stack.append([node.left, currPathSum, cache.copy()])
            if node.right:
                stack.append([node.right, currPathSum, cache.copy()])
        
        return result

113 https://leetcode.com/problems/path-sum-ii/

from collections import deque

class Solution(object):
    def pathSum(self, root, target):
        if not root:
            return []
        stack = deque([[root, root.val, [root.val]]])
        ret = []
        while stack:
            node, _sum, history = stack.pop()  # [현재노드, 현재까지의 합, 현재까지의 노드 히스토리]
            is_leaf = not node.left and not node.right
            if _sum == target and is_leaf:  # 현재까지의 합과 target이 같고 leaf노드인 경우엔 답이다.
                ret.append(history)
            if node.left:
                stack.append([node.left, _sum + node.left.val, history + [node.left.val]])
            if node.right:
                stack.append([node.right, _sum + node.right.val, history + [node.right.val]])
        return ret

82 https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

class Solution(object):
    def deleteDuplicates(self, head):
        dummy = ListNode(0, head)  # 더미를 하나 만들어둠.
        prev = dummy
        while head and head.next:
            cur = head
            next = head.next
            if cur.val == next.val:  # 현재와 다음값이 같을경우
                while next and cur.val == next.val:  # 다음값이 있으면서 다음값이랑 현재값이랑 다를때까지 계속 전진함.
                    next = next.next
                prev.next = next  # 삭제를 위해 prev.next를 next로
                head = next
            else:
                prev = head  # 현재와 다름값이 다를경우 정상이므로 한칸 이동
                head = head.next
        return dummy.next

83 https://leetcode.com/problems/remove-duplicates-from-sorted-list/

82하고 거의 비슷함.

class Solution(object):
    def deleteDuplicates(self, head):
        dummy = ListNode(0, head)
        while head and head.next:
            cur = head
            next = head.next
            if cur.val == next.val:
                while next and cur.val == next.val:
                    next = next.next
                cur.next = next
                head = next
            else:
                head = head.next
        return dummy.next