[Binary Tree][Medium] 437. Path Sum III

 

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

 

 

Q. 주어진 노드에서 경로합이 targetSum이 되는 모든 경로의 수를 구하라. 

 이때 경로는 특정 노드에서 아래 방향으로만 해당된다. 

 

 

Solution. 

 특정 노드 root를 기준으로 먼저 생각해 보자. 

 root 에서 아래로 방문하는 노드의 값을 누적한 후, 그 값이 targetSum과 같으면 root에서 해당되는 경로가 있는 것이다. 

 이 연산을 모든 노드에 대해 수행한다. 

 

 

    void pathSum_dfs(TreeNode* node, int targetSum, long sum, int& pathCnt, unordered_set<TreeNode*>& setChecked)
    {
        if(node == NULL)    
            return;

        sum += node->val;
        if(sum == targetSum)
            ++pathCnt;
        
        pathSum_dfs(node->left, targetSum, sum, pathCnt, setChecked);
        pathSum_dfs(node->right, targetSum, sum, pathCnt, setChecked);
        
        if(setChecked.find(node->left) == setChecked.end())
        {
            setChecked.insert(node->left);
            pathSum_dfs(node->left, targetSum, 0, pathCnt, setChecked);
        }
        if(setChecked.find(node->right) == setChecked.end())
        {
            setChecked.insert(node->right);
            pathSum_dfs(node->right, targetSum, 0, pathCnt, setChecked);
        }
    }

public:
    int pathSum(TreeNode* root, int targetSum) 
    {
        unordered_set<TreeNode*> setChecked;
        int pathCnt = 0;
        setChecked.insert(root);
        pathSum_dfs(root, targetSum, 0, pathCnt, setChecked);
        return pathCnt;
    }

 

하위 7%에 해당하는 속도결과를 얻었다. 

일반적인 solution과 동떨어진 풀이라는 것이다. 

다시 생각해 본다. 

 

 

알고리즘 풀이과정에서 가장 경계해야 할 것 중의 하나는, 

루핑과정을 가급적 되풀이 하지 않는 것이다. 

한번 로직을 수행할때 할수 있으면, 그때 하는 것이다. 

다시 방문하지 않도록 해야 한다. 

그렇다면, 모든 노드에서의 누적 값 정보를 한번 방문 시 다 알아야 한다. 

또한 그 누적값은 다시 parent로 돌아갈 시, 다시 감해 주어야 다른쪽 누적에 방해 주지 않게 된다. 

 

정리하고 보니, 어디서 많이 본 느낌이다. 

backtrack 방식의 해결을 binary tree에 접목하면 될 것 같다. 

 

 

    void pathSum_dfs(TreeNode* node, int targetSum, int& pathCnt, vector<long>& vSums)
    {
        if(node == NULL)    
            return;

        // 새로 방문한 노드를 추가해 준다.
        vSums.push_back(0);
        for(int q = 0; q < vSums.size(); ++q)
        {
            // 누적값을 구하고, targetSum인지 check 한다.
            vSums[q] += node->val;
            if(vSums[q] == targetSum)
                ++pathCnt;
        }

        pathSum_dfs(node->left, targetSum, pathCnt, vSums);
        pathSum_dfs(node->right, targetSum, pathCnt, vSums);

        // exit 할때는 누적값을 다시 제해 준다.
        for(int q = 0; q < vSums.size(); ++q)
            vSums[q] -= node->val;
        vSums.pop_back();
    }

public:
    int pathSum(TreeNode* root, int targetSum) 
    {
        vector<long> vSums;
        int pathCnt = 0;
        pathSum_dfs(root, targetSum, pathCnt, vSums);
        return pathCnt;
    }

 

적절한 결과를 얻었다. - 좋은 문제.