(C++) - LeetCode (easy) 112. Path Sum

https://leetcode.com/problems/path-sum/

Path Sum - LeetCode

leaf node 특징을 파악해 푼 문제였습니다.

📕 풀이방법

📔 풀이과정

말단 node로 가는 여러 경로별로 조건을 확인하는 방법은 재귀함수가 편합니다.

1. 현재 node가 NULL인 경우 : 처음부터 빈 tree이거나 말단 node에 도달하지 못한 경우에 해당합니다. 

2. 말단 node인 경우 : 왼쪽과 오른쪽 자식이 없는 경우이므로 이 때 sum을 계산해 targetSum인지를 확인해줍니다. 새로운 함수를 재귀적으로 호출할 때 자신의 node->val을 더하면서 인자로 넘겨주므로 말단 node에서 targetSum인지 여부를 판별할 때 sum + node->val과 같은지를 비교해야 합니다.

3. 왼쪽과 오른쪽 자식에 대해 valid여부를 검사합니다.

---

📕 Code

📔 C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        return isValid(root, targetSum, 0);
    }
    
    bool isValid(TreeNode* node, int targetSum, int sum) {
        if(node == NULL) {
            return false;
        }
        if(node->left == NULL && node->right == NULL){
            if(targetSum == sum + node->val) return true;
            return false;
        }
        bool isLeftValid = isValid(node->left, targetSum, sum + node->val);
        bool isRightValid = isValid(node->right, targetSum, sum + node->val);
        return max(isLeftValid, isRightValid);
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.