리트코드 112번

나의 풀이

var hasPathSum = function(root, targetSum) {
    let count = 0;    
    
    if (!root) {
        return false;
    }
    
    function DFS(root, targetSum) {
        if (!root.left && !root.right) {
            // console.log(root.val, targetSum);
            if (targetSum-root.val === 0) count = 1;
            return;
        }
        targetSum -= root.val;
        if (root.left) {
            DFS(root.left, targetSum);
        }
        if (root.right) {
            DFS(root.right, targetSum);    
        }
        targetSum += root.val;
        
    }
    DFS(root, targetSum);
    

    return count === 1;

    
};

DFS를 이용해서 탐색하면서 root.val을 targetSum에 빼주고, node의 children이 없는 경우, targetSum이 0이면 count를 1로 바꿔준다. 그리고 리턴한다. 탐색이 끝나고 count가 1이면 true 그렇지 않으면 false를 리턴한다.

좋은 웹페이지 즐겨찾기