[Easy] LeetCode - no.112 Path Sum : Java

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

 

 

문제

이진 트리의 root와 정수 targetSum이 주어졌을 때, 트리의 루트로부터 리프까지의 합이 targetSum과 일치하는지 여부를 판단할 것

 

Example 1

 

 

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

 

 

 

 

 

 

풀이

참고

LeetCode 112(Path Sum, java)

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

        if (targetSum - root.val == 0 && root.left == null && root.right == null) {
            return true;
        }

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

• 조건 1 : root가 리프 노드를 넘었다면 false 반환
• 조건 2: targetSum에서 root.val을 뺀 값이 0이고, 왼쪽과 오른쪽 노드가 null이라면 (root가 리프 노드라면) true 반환
• 재귀 호출 : 왼쪽 노드와 targetSum - root.val, 오른쪽 노드와 targetSum - root.val을 인자로 넘기고, 둘 중 하나라도 충족되는 것이 있다면 true 
• 시간복잡도 : O(N)