LeetCode 112. Path Sum 자바 문제 풀이

문제

LeetCode - The World's Leading Online Programming Learning Platform

문제 해결 방법

• 이 문제의 목적은, 주어진 이진 트리에서 루트부터 잎 노드까지의 경로 중 합이 주어진 targetSum과 같은 경로가 있는지 확인하는 것입니다.
• 그러므로, 이 코드는 주어진 이진 트리에서 재귀적으로 경로를 탐색하고, 경로 합이 targetSum과 같은지 확인합니다.

알고리즘

1. 재귀 함수 호출 (Recursion):
   • hasPathSum 함수는 재귀적으로 호출됩니다.
   • 이 함수는 현재 노드의 값을 targetSum에서 빼고, 이 값을 새로운 targetSum으로 사용합니다.
2. 기본 케이스 (Base Case):
   • 재귀 호출이 시작될 때, 현재 노드가 null인지 확인하여 트리의 끝에 도달했는지 검사합니다.
   • 만약 null이라면, 현재 경로는 유효하지 않으므로 false를 반환합니다.
3. 잎 노드 확인 (Leaf Node Check):
   • 현재 노드가 잎 노드인지 확인합니다. 잎 노드는 자식 노드가 없는 노드입니다.
   • 현재 노드가 잎 노드인 경우, targetSum이 0과 같은지 확인합니다.
   • targetSum이 0과 같다면, 현재 경로의 합이 targetSum과 일치하므로 true를 반환합니다.
4. 왼쪽과 오른쪽 서브트리 재귀 호출 (Recursive Calls):
   • 현재 노드가 잎 노드가 아닌 경우, 왼쪽 서브트리와 오른쪽 서브트리에 대해 hasPathSum 함수를 재귀적으로 호출합니다.
   • 재귀 호출 시, 현재 노드의 값을 뺀 targetSum을 사용하여 경로를 탐색합니다.
5. 결과 반환 (Return):
   • 왼쪽 서브트리와 오른쪽 서브트리 중 하나라도 true를 반환하면, 현재 경로에서 targetSum을 만족하는 경로가 존재하므로 true를 반환합니다.
   • 그렇지 않으면 false를 반환합니다.

재귀함수 구현 표

• 목표: https://leetcode.com/problems/path-sum/
• 종료 조건 (Base Case):
• if root==null return false if left==null && right==null <- after sum-=root.val return sum==0
• 이전단계의 결과가 필요한가?: yes
• 문제분할 (Divide the Problem):
• sum-=root.val
• 결과의 조합:
• boolean left boolean right return left||right
• 재귀호출, 다음 단계로 가기전 변경 할점 (Recursive Call):
• sum-=root.val

Github Link

https://github.com/eunhanlee/LeetCode_112_PathSum_Solution.git

시간복잡도: O(n), 공간복잡도: O(h)

class Solution {

    /**
     * 주어진 이진 트리에서 루트에서 리프 노드까지의 경로가 주어진 목표 합계와 일치하는지 확인합니다.
     *
     * @param root      이진 트리의 루트 노드입니다.
     * @param targetSum 목표 합계입니다.
     * @return 경로가 존재하면 {@code true}를 반환하고, 그렇지 않으면 {@code false}를 반환합니다.
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        // 현재 노드의 값을 목표 합계에서 빼줍니다.
        targetSum -= root.val;

        // 현재 노드가 리프 노드이며 목표 합계가 0인지 확인합니다.
        if (root.left == null && root.right == null) {
            return targetSum == 0;
        }

        // 왼쪽 및 오른쪽 서브트리를 재귀적으로 확인합니다.
        Boolean rightNode = hasPathSum(root.right, targetSum);
        Boolean leftNode = hasPathSum(root.left, targetSum);

        // 왼쪽 또는 오른쪽 서브트리 중 하나에 유효한 경로가 있는 경우 true를 반환합니다.
        return rightNode || leftNode;
    }
}

시간 복잡도

• 이 코드의 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)입니다. 여기서 n은 트리의 노드 수입니다.

공간 복잡도

• 재귀 함수 호출에 따라 호출 스택이 쌓이지만, 최대 트리의 높이까지만 스택이 필요하므로 공간 복잡도는 O(h)입니다. 여기서 h는 트리의 높이입니다.