Leetcode Java Path Sum

문제

Link

코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

  public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
      return false;
    } else if (root.left == null && root.right == null && targetSum - root.val == 0) {
      return true;
    } else {
      int sum = targetSum - root.val;
      return this.hasPathSum(root.left, sum) || this.hasPathSum(root.right, sum);
    }
  }

}

결과

Link

설명

1. 주어진 TreeNode인 root의 마지막 노드까지의 val 값들의 합이 targetSum이 되는 줄기가 존재하는지 검증하는 문제이다.

2. 재귀 호출을 이용하여 targetSum과 동일한지를 검증하고 주어진 문제의 결과로 반환한다.

   • root가 null인 경우 존재하지 않은 노드 혹은 주어진 문제의 TreeNode가 null인 경우이므로, false를 반환한다.
   • root의 left와 right가 null이면 마지막 노드이므로, $targetSum - root.val$이 0인 경우 true를 반환한다.
   • 그 외의 경우는 마지막 노드가 아니므로, root의 left와 right TreeNode를 $targetSum - root.val$ 값으로 재귀 호출을 수행한 결과들의 OR(논리합) 결과를 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.