Songzi Vong
공부 저장소
알고리즘, 자료구조, 정리노트 모음

112. Path Sum

112. Path Sum

문제

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

문제 사이트

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.

Example 2: Input: root = [1,2,3], targetSum = 5 Output: false Explanation: There are two root-to-leaf paths in the tree:

(1 –> 2): The sum is 3. (1 –> 3): The sum is 4. There is no root-to-leaf path with sum = 5.

Example 3: Input: root = [], targetSum = 0 Output: false Explanation: Since the tree is empty, there are no root-to-leaf paths.

Constraints:

The number of nodes in the tree is in the range [0, 5000]. -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000

문제 해석

  • 이진 트리에서 ‘targetsum’을 리프 노드까지의 경로들의 val로 만들수 있는지 묻는 문제이다.
  • 만약 경로상에 targetsum을 만들 수 있다면 true 만들 수 없다면 false를 리턴하면 된다.

생각

  • 리프 노드까지 내려간 값들을 다 저장해놔야한다.
  • 숫자를 저장하는 sum 변수가 필요할 것 같다.

구현

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root)   return false;
        if(root->left == NULL && root->right == NULL && root->val == targetSum) return true;
        return hasPathSum(root->left, targetSum-root->val) || hasPathSum(root->right, targetSum-root->val);
    }
};

코드 해석

  • Binary Tree 에는 Top-bottom 과 bottom-up 방식이 있다. 말 그대로 위에서부터 아래로 해석하며 코드를 짤 것이냐 와 아래에서부터 위로 해석하며 코드를 짤 것이냐 의 차이이다.
  • 해당 문제는 루트노드부터 val의 숫자들을 뺄셈하며 아래로 내려가는 방법으로 Top-bottom 방식이 더 어울리는 것이다. 이렇게 문제를 보고 어떤 방식의 알고리즘이 더 효율적인지 생각해야 한다.
if(!root)   return false;
  • example3 의 조건 : 루트가 존재하지 않으면 false 출력
if(root->left == NULL && root->right == NULL && root->val == targetSum) return true;
  • 만약 리프 노드까지 내려갔을 때 리프 노드의 값과 targetSum이 같다면 최종적으로 뺄셈 결과가 0이 도출되므로 경로상의 targetSum이 존재한다는 뜻이다.
return hasPathSum(root->left, targetSum-root->val) || hasPathSum(root->right, targetSum-root->val);
  • 재귀적인 호출로 노드의 값을 빼가며 최종적으로 ‘0’ 을 도출해 경로상에 targetSum이 존재하는지 찾는 방법이다.

후기

**재귀적 호출 코드 짜는 방법 계속 공부하기 + 복습하기**

Table of Contents