LeetCode 112번 - Path Sum

문제 소개

이진 트리와 int형 변수 targetSum이 주어진다.

 

루트 노드부터 리프 노드(자식 노드가 없는 노드)까지 키 값을 누적하면서 내려간다고 할 때, 누적한 값이 targetSum과 같아지는 경로가 있는지 확인해야 한다.

 

---

살펴보기

checkPathSum(TreeNode root, int targetSum) 메서드를 호출해 루트 노드부터 리프 노드가 나올 때까지 targetSum을 전달하면서 이동했다.

 

먼저 targetSum에서 현재 노드의 키 값을 차감한 후, 현재 노드가 리프 노드인지 확인했다.

 

만약 현재 노드가 리프 노드가 아닌 경우, 왼쪽 자식 노드와 오른쪽 자식 노드가 있는지 확인했다.

해당 노드가 있는 경우, checkPathSum()를 다시 호출해 다음 자식 노드와 targetSum을 전달했다. 

 

그러나 현재 노드가 리프 노드인 경우 targetSum을 확인하고, targetSum이 0이면 0을, 0이 아니면 1을 반환하게 했다.

이 때 targetSum이 0이면 루트 노드부터 해당 리프 노드까지의 키 값을 누적한 값이 targetSum과 같다고 할 수 있다.

 

checkPathSum()함수의 처리결과는 int 자료형의 변수 left와 right에 저장한 다음, 두 값을 곱해 호출한 곳으로 반환한다.

 

만약 키 값의 누적값이 targetSum과 같아지는 경로가 하나라도 있다면, left와 right 둘 중 하나에 0이 있게 되므로 두 값의 곱은 0이 된다

 

호출한 checkPathSum(TreeNode root, int targetSum) 함수의 처리가 전부 끝나면 그 결과값을 확인해서 0인 경우 true를 반환했다!

 

---

풀어보기

public boolean hasPathSum(TreeNode root, int targetSum) {
    if(root==null) return false;

    if(root!=null){
        if(checkPathSum(root, targetSum) == 0) return true;
    }

    return false;
}

public int checkPathSum(TreeNode root, int targetSum){
    targetSum -= root.val;

    if(root.left==null && root.right==null) {
        if(targetSum==0) return 0;
        else return 1;
    }

    int left = 1;
    int right = 1;

    if(root.left!=null) left = checkPathSum(root.left, targetSum);
    if(root.right!=null) right = checkPathSum(root.right, targetSum);

    return left * right;
}