[알고리즘 연습] 트리 경로의 합

트리 경로의 합

• 루트 노드와 임의의 수 'targetSum'을 주어, 루트 노드부터 리프 노드까지 가는 경로의 합 중 targetSum과 일치하는 값이 있는지 확인한다.
• 하나라도 일치하면 True를 리턴하고, 일치하는 수가 없으면 False를 리턴한다.

---

풀이

class Node():
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def path_sum(node, targetSum):

    def path_sum(now_node, now_sum):
        if (now_node.left == None) and (now_node.right == None):
            now_sum += now_node.val
            return [now_sum]
        else:
            now_sum += now_node.val
        return path_sum(now_node.left, now_sum) + path_sum(now_node.right, now_sum)     

    sum_lst = path_sum(node, 0)
    for n in sum_lst:
        if n == targetSum:
            return True

    return False

• 트리 전체를 체크하기 위해 재귀함수를 사용했다.
• 0부터 시작해서 현 노드의 값을 더해나가며, stop 조건이 되어주는 리프노드에서는 해당 값을 리스트 형태로 리턴한다.
• 그리고 그렇게 형성된 모든 경로의 합들이 저장되어 있는 리스트를 돌면서 targetSum과 일치하는 값이 있는지 체크한다.