[LC] 113. Path Sum II

[seungriyou]

<113. Path Sum II>

Approach

Idea 1: Backtracking

backtracking 시 주의해야 할 점은 현재 보고 있는 node가 leaf node 인지를 확인해야 한다는 점이다.

left node 일 때와 아닐 때 모두 공통적으로 수행해야 할 작업은 따로 빼면 코드의 중복을 방지할 수 있다.

backtracking 로직은 다음과 같이 작성할 수 있다.

def get_path_sum(node, remaining_val):
    # base condition
    if not node:
        return

    # common work
    remaining_val -= node.val
    tmp_path.append(node.val)

    # <1> if given node is leaf node, record
    if not node.left and not node.right:
        # targetSum과 현재까지의 sum_val이 같다면(= remaining_val이 0이라면), tmp_path 기록
        if not remaining_val:
            res.append(tmp_path[:])
    # <2> else, recur
    else:
        get_path_sum(node.left, remaining_val)
        get_path_sum(node.right, remaining_val)
    
    # common work
    tmp_path.pop()

get_path_sum(root, targetSum)

Idea 2: Iterative w/ Stack

while 문을 이용하여 iterative 한 방식으로도 해결할 수 있다. queue를 사용할 필요가 없으므로 간단하게 stack을 사용했다.

그런데 이처럼 tmp_path + [node.xxxx.val]로 tmp_path를 확장시키는 것은 copy 작업이 필요하기 때문에 복잡도 측면에서 별로 좋지 않을 것 같다는 생각이다..

res, stack = [], []

if root:
    stack.append((root, targetSum - root.val, [root.val]))

while stack:
    node, remaining_val, tmp_path = stack.pop()

    if not node.left and not node.right and not remaining_val:
        res.append(tmp_path[:])
    
    if node.left:
        stack.append((node.left, remaining_val - node.left.val, tmp_path + [node.left.val]))
    
    if node.right:
        stack.append((node.right, remaining_val - node.right.val, tmp_path + [node.right.val]))

Complexity

• Time: O(n^2) (모든 node 한 번씩 방문 & leaf node까지 도달할 때마다 targetSum과 같다면 tmp_path 원소 copy) (height의 최댓값은 n이므로)
• Space: O(height) (output을 제외하면, call stack은 tree의 height) (balanced tree라면 O(log n), skewed tree라면 O(n))