leetcode - Tree - Path Sum

 

이번 문제는 인자로 binary tree와 int형 sum 값이 주어지며,

트리의 최상단에서 마지막 노드까지의 val을 sumation한 값이 인자로 주어진 sum값과 같은 경우가 있는지 판단하는 문제입니다.

 

저의 경우 leaf 노드를 만날때까지 탐색을 하였고, 리프노드에 도달했을때 값을 비교하여 boolean 값을 반환하도록 하였습니다.

 

값이 같다면 True를 반환시켰고, or 연산으로 왼쪽-오른쪽 노드 탐색을 묶어서 하나라도 sum이 같은 길을 찾으면 True로 반환되도록 하였습니다.

 

아래는 코드입니다.

 

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

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:

        if not root: return False
        res = self.findTree(root, sum, 0)
        return res

    def findTree(self, root: TreeNode, sum:int, additional_sum: int):
        if root: additional_sum += root.val
        if not root: return 
        if root.left == None and root.right == None:
            if sum == additional_sum: return True
            else: return False
        return self.findTree(root.right, sum, additional_sum) or self.findTree(root.left, sum, additional_sum)