LeetCode - 경로 합계

문제 설명

이진 트리의 루트와 정수 targetSum이 주어지면,
트리에 루트에서 리프까지의 경로가 있는 경우 true를 반환합니다.
경로의 모든 값은 targetSum과 같습니다.

리프는 자식이 없는 노드입니다.

문제 진술 출처: https://leetcode.com/problems/path-sum

예 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.

예 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 a sum = 5.

예 3:

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

제약:

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

설명

재귀

대부분의 트리 관련 문제를 해결하기 위한 가장 좋은 방법은 재귀 접근 방식을 사용하거나 큐/스택을 사용하는 것입니다.

재귀를 사용하여 해결할 수 있는 쉬운 문제 중 하나입니다. 주어진 단계에 따라 문제를 해결합니다.

왼쪽 및 오른쪽 하위 트리로 재귀적으로 이동합니다. 각 재귀 호출에서 합계를 현재 노드 값만큼 줄입니다.

임의의 재귀 호출에서 현재 노드 값이 나머지 합계와 같으면 true를 반환합니다. 이는 주어진 대상과 함께 경로가 존재함을 의미합니다.

먼저 알고리즘을 확인해 봅시다.

- if root == null
  - return false

- if root->val == targetSum && root->left == null && root->right == null
  - return true

- remainingTarget = targetSum - root->val

- return hasPathSum(root->left, remainingTarget) || hasPathSum(root->right, remainingTarget)

C++, Golang, Javascript에서 알고리즘을 확인해 봅시다.

C++ 솔루션

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == NULL) {
          return false;
        }

        if(root->val == targetSum && root->left == NULL && root->right == NULL) {
            return true;
        }

        int remainingTarget = targetSum - root->val;

        return hasPathSum(root->left, remainingTarget) || hasPathSum(root->right, remainingTarget);
    }
};

골랑 솔루션

func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }

    if root.Val == targetSum && root.Left == nil && root.Right == nil {
        return true
    }

    remainingTargetSum := targetSum - root.Val

    return hasPathSum(root.Left, remainingTargetSum) || hasPathSum(root.Right, remainingTargetSum)
}

자바스크립트 솔루션

var hasPathSum = function(root, targetSum) {
    if(root == null) {
        return false;
    }

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

    let remainingTarget = targetSum - root.val;

    return hasPathSum(root.left, remainingTarget) || hasPathSum(root.right, remainingTarget);
};

예제 1의 알고리즘을 시험 실행해 보겠습니다.

Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]
       targetSum = 22

Step 1: if root == null
           the root is at 5
           false

Step 2: if root->val == targetSum && root->left == NULL && root->right == NULL
           5 == 22
           false

Step 3: remainingTarget = targetSum - root->val
                        = 22 - 5
                        = 17

Step 4: return hasPathSum(root->left, remainingTarget) ||
                 hasPathSum(root->right, remainingTarget)

        root->left = 4
        root->right = 8
        remainingTarget = 17

Step 5: if root == null
           the root is at 4
           false

Step 6: if root->val == targetSum && root->left == NULL && root->right == NULL
           4 == 17
           false

Step 7: remainingTarget = targetSum - root->val
                        = 17 - 4
                        = 13

Step 8: return hasPathSum(root->left, remainingTarget) ||
                 hasPathSum(root->right, remainingTarget)

        root->left = 11
        root->right = nil
        remainingTarget = 13

Step 9: if root == null
           the root is at 11
           false

Step 10: if root->val == targetSum && root->left == NULL && root->right == NULL
           11 == 13
           false

Step 11: remainingTarget = targetSum - root->val
                        = 13 - 11
                        = 2

Step 12: return hasPathSum(root->left, remainingTarget) ||
                 hasPathSum(root->right, remainingTarget)

        root->left = 7
        root->right = 2
        remainingTarget = 2

Step 13: if root == null
           the root is at 7
           false

Step 14: if root->val == targetSum && root->left == NULL && root->right == NULL
           7 == 2
           false

Step 15: remainingTarget = targetSum - root->val
                         = 2 - 7
                         = -5

Step 16: return hasPathSum(root->left, remainingTarget) ||
                 hasPathSum(root->right, remainingTarget)

        root->left = null
        root->right = null
        remainingTarget = -5

Step 17: if root == null
            the root is null
            true

          We backtrack to Step 16

Step 18: if root == null
            the root is null
            true

          We backtrack to Step 12

Step 19: if root == null
           the root is at 2
           false

Step 20: if root->val == targetSum && root->left == NULL && root->right == NULL
           2 == 2
           true

We return true here and backtrack for the rest of the tree. In the end, we have OR condition and have found the path once we return the answer as true.