문제
Approach 1. Recursion
내 솔루션이다!
class Solution:
def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
if not root: [1]
return False
if not root.left and not root.right: [3]
return targetSum == root.val
targetSum -= root.val [2]
return self.hasPathSum(root.left,targetSum)\
or self.hasPathSum(root.right, targetSum) [4]접근 방식
크게 보면 resursion, 재귀함수이다.
재귀함수를 부른다면 base case가 있어야하고, 계속 업데이트 해주는 값이 있어야한다.
[1] base case이다.
root가 None이면 return False를 한다.
[2] 만약 root가 None이 아니라면 targetSum에서 현재 root.val을 빼서 targetSum을 업데이트해준다.
이렇게 해주는 것은 나중에 root에 children이 없다면 (마지막 leaf라면) root의 상단의 값들을 빼면서 내려온 targetSum과 root.val을 비교해주기 위함이다.
[4] root의 왼쪽, 오른쪽에 각각 함수를 부른다. 둘중에 하나만 True여도 답은 True이기 때문에, or를 써준다.
이때 함수는 root.left과 root.right을 가지고 다시 [1]로 돌아가서 체크를 한다.
[3][2]에서 설명했듯 root의 왼쪽과 오른쪽이 둘다 None인 경우 (마지막 leaf인 경우)에는 targetSum과 root의 value가 같은지 본다.
Approach 2. DFS
class Solution(object):
def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
if not root: [1]
return False
stack = [(root, targetSum - root.val)] [2]
while stack: [3]
u = stack.pop() [4]
if not u[0].left and not u[0].right: [5]
if u[1] == 0: [6]
return True
if u[0].left: [7]
stack.append((u[0].left, u[1]-u[0].left.val))
if u[0].right: [8]
stack.append((u[0].right, u[1]-u[0].right.val))
return False [9]접근 방식
DFS 방식은 다른 사람이 한 것을 가져와서 분석해보았다.
프린트를 해보니 아래와 같이 탐색을 했다. 
[1] root가 None이면 False를 리턴한다.
[2] root가 None이 아니라면 stack에 트리 그 자체와 targetSum에서 root.val을 뺀 값을 담는다.
targetSum을 업데이트를 해주는 것.
[3] stack이 None일때까지 while loop을 돌린다. 만약 stack이 None인데 [6]에서의 조건이 만족되지 않고 리턴 True가 안된다면 [9]로 가서 return False를 하는 형식이다.
[4] stack.pop()을 한 값을 u에 담는다. u는 Tree와 업데이트 된 targetSum이 있다.
[5] u[0]은 Tree이다. Tree의 왼쪽과 오른쪽 노드가 다 None인 경우이다.
[6][5]의 조건에 부합한다면 최하단 노드인 것이므로 업데이트된 TargetSum, u[1]이 0인지와 비교한다. 맞으면 True를 리턴한다. 아니면 다른 곳으로 가서 탐색을 진행할 것이다.
[7] 만약 Tree의 왼쪽, 오른쪽 노드가 둘다 None이 아니던가, 혹은 [6]에서 return False였다면 탐색을 새로이 진행한다.
Tree의 왼쪽 노드가 None이 아니라면 stack에 새롭게 left Tree, 그리고 left Tree의 최상단 노드의 값을 빼준 targetSum을 넣어준다. 그렇다면 이 stack은 다시 [3]으로 올라가서 탐색을 반복할 것이다.
[8][7]과 마찬가지로 Tree의 오른쪽 노드가 None이 아닌 경우에 탐색을 진행한다.
[9] 만약 Tree 전체를 다 돌았는데 최하단 node에서 targetSum이 0이 아니었다면 return False를 해준다.
소소한 후기
일주일 내내 DFS, BFS만 풀다보니까 실력이 늘었다...!!! 힌트 한번도 안 보고 5분만에 optimal solution 내본 적 처음이다. 감동 감동 왕감동이다.
앞으로도 리트 코드 풀면서 열심히 잔디를 심어야지.
