LeetCode - Path Sum

문제 요약

function TreeNode(val, left, right) {

    this.val = (val===undefined ? 0 : val)

    this.left = (left===undefined ? null : left)

    this.right = (right===undefined ? null : right)

 }

트리와 targetSum이 주어진다
리프노드까지 경로를 모두 더했을 때 targetSum과 동일한 값을 가질 수 있으면 true
없으면 false를 반환한다

예시

1. 입력: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
   출력: true
2. 입력: root = [1,2,3], targetSum = 5
   출력: false
3. 입력: root = [], targetSum = 0
   출력: false

풀이

var hasPathSum = function(root, targetSum) {
    if(!root) return false;
    if(!root.left && !root.right){
        return root.val === targetSum;
    }
    return hasPathSum(root.left, targetSum-root.val)||hasPathSum(root.right, targetSum-root.val);

};

• 재귀적으로 왼쪽 or 오른쪽으로 계속 내려가며 targetSum에서 현재 값을 뺀다
• 해당 노드가 left와 right가 없는 리프노드라면 targetSum과 현재 노드의 val를 검사해 같은 값이면 true를 반환한다
• root가 없다면 false를 반환한다
• hasPathSum에 or를 하여 둘중 하나라도 true가 반환되면 true를 출력한다

시간복잡도 : O(n) -> n은 노드의 개수수