리트코드 - 112. Path Sum

리트코드 - 112. Path Sum

출처 - https://leetcode.com/problems/path-sum/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

이진 트리의 root와 정수 targetSum이 주어지면, 경로를 따라 모든 값을 더하면 targetSum이 되는 루트-리프 경로가 트리에 있으면 true를 반환합니다. 리프는 자식이 없는 노드입니다.

 

의사코드

함수 hasPathSum(root, targetSum) if (root == null)     false 리턴 if (root의 left == null && root의 right == null)     targetSum - root의 val == 0 리턴 hasPathSum(root의 left, targetSum - root.val) || hasPathSum(root의 right, targetSum - root.val) 리턴

 

풀이코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        
        if (root.left == null && root.right == null) {
            return targetSum - root.val == 0;
        }

        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

 

코드설명

함수를 이용하여 재귀적으로 구현한 방법이다.

먼저 큰 틀에서 설명하자면 DFS 방식으로 내려가는데 root부터 leaf까지 더해야 한다.

단순히 sum을 이용하면 계산하기가 무척 애매해지기 때문에 targetSum에서 값을 빼서 매개변수로 전달시키는 방법을 선택했다.

 

노드를 거칠때 마다 root의 val값을 빼주기 위해 매개변수에 targetSum - root.val 를 전달해준다.

만일 leaf에 도달했다고 가정한다면 root.left와 root.right이 모두 null 일 것이다.

이 때 targetSum에서 root의 val값을 빼서 0이면 true를 리턴한다.

만약 0이 아니라면 false를 리턴할 것이다.

 

둘 중 하나만 true여도 true가 되는 or 연산이기 때문에 결과적으로 조건을 만족하는지 확인할 수 있다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

root에서 더한 sum값은 가지고 있어야 한다.

라고 생각하다보니 sum을 지역변수로 처음에는 만들었었는데 아무리 생각해도 활용하기가 어려웠다.

더했다 뺐다 하기도 번거롭고... 스파게티 코드가 되기 1초전이었다.

 

그러다가 매개변수가 두 개인 것을 보고 반대로 빼야겠다는 생각을 했고, 결과적으로 옳은 정답을 얻을 수 있었다.

 

다른 코드

public boolean hasPathSum(TreeNode root, int targetSum) {
    // 2. Iteration - BFS
    if(root == null) return false;
    Queue<TreeNode> q = new LinkedList<>();
    Queue<Integer> n = new LinkedList<>();
    q.offer(root);
    n.offer(root.val);
    while(!q.isEmpty()){
        TreeNode cur = q.poll();
        Integer sum = n.poll();
        if(cur.left == null && cur.right==null) { // leaf node
            if(sum == targetSum) return true;
        }
        if(cur.left != null){
            q.offer(cur.left);
            n.offer(cur.left.val + sum);
        }
        if(cur.right != null){
            q.offer(cur.right);
            n.offer(cur.right.val + sum);
        }
    }
    return false;

BFS방식으로 탐색하는 방법도 있다.

런타임은 2ms 로 최악(?)이지만 메모리는 오히려 최상(99%)이었다.

queue 두개를 이용해서 node와 sum을 계산하는 방식이 무척 깔끔하고 좋은 것 같다.

이 코드는 BFS 활용을 위해 암기해두어도 좋을 것 같다.

 

정리

root-leaf를 순회할때 DFS, BFS 사용하는 방법들 각각 기억하기