[LeetCode] 112. Path Sum

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

Path Sum - LeetCode

Path Sum

 

Path Sum 시리즈 첫번째다.

 

 

이진 트리가 주어졌을때, 루트 노드부터 마지막 노드까지 더해 targetSum이 하나라도 나오는지 출력하는 문제다.

풀이는

루트 노드부터 자식 노드들을 쭉 방문하면서 해당 노드의 값을 부모노드+해당노드 의 값으로 업데이트를 해준다.

그리고 left, right 자식이 없을 경우 targetSum과 이 노드값을 비교해주면 된다.

 

전체 풀이 코드

class Solution {
public:
    int targetSum;
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        this->targetSum = targetSum;
        return run(root);
    }
    bool run(TreeNode* node) {
        bool l=false,r=false;
        if (node->left) {
            node->left->val+=node->val;
            l = run(node->left);
        }
        if (node->right) {
            node->right->val+=node->val;
            r = run(node->right);
        }
        return (!node->left && !node->right)? node->val==this->targetSum:l||r;
    }
};