(Easy - DFS) Leetcode - 112. Path Sum

트리가 주어지면 root 노드에서 leaf 노드로 가는 경로 중 노드들의 값의 합이 targetSum과 같은 경로가 하나라도 있는지 찾는 문제입니다.

경로를 찾는 문제이므로 DFS를 사용했습니다.

Leaf 노드는 자식 노드들이 없는 노드를 Leaf 노드로 정의합니다.

 

bool DFS(TreeNode* node, int sum, const int& targetSum) {
        if (!node) 
            return false;

        sum += node->val;

        if (!node->left && !node->right) // Leaf node
            return sum == targetSum; // 같은지 확인
		
        // 왼쪽경로 || 오른쪽 경로 
        return DFS(node->left, sum, targetSum) || DFS(node->right, sum, targetSum);
    }
    
    bool hasPathSum(TreeNode* root, int targetSum) {
		if (!root) return false;
        return DFS(root, 0, targetSum);
    }

위의 방법은 int 변수 sum을 정의해 값을 계속 더해 targetSum과 비교하는 방식입니다.

 

하지만 조금 다르게 생각하면 경로의 모든 값을 targetSum에 뺄셈을 해 targetSum이 0이 된다면 경로의 합이 targetSum과 같은 것이고 0이 아닌 음수나 양수가 된다면 다르다는 의미가 될 수 있습니다.

 

그러면 DFS 함수 없이 정답을 찾을 수 있습니다.

 

    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;

        if (!root->left && !root->right)
            return root->val == targetSum;

        targetSum -= root->val;
        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
    }