Leetcode - 113. Path Sum II

문제

targetSum 값과 트리가 주어질때, 루트 노드부터 leaf까지 path의 합이 targetSum이 되는 path를 모두 찾아라.

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

해결 아이디어

• DFS로 순회하면서 모두 합을 더하여 pathsum값인지 확인. left/right 두개짜리 backtracking 이다.
• 루트부터 leaf까지 모두 더하는 합이다(첨엔 중간까지 인줄알아서 햇갈림. 아래 주석#2참고)

해결

• tmp배열에 push_back()하고 pop_back()하는걸 쌍으로 해야함. 처음에 아래 #3을 빼먹어서 디버깅을 오래함.
• #1 음수값으로 이루어진 트리의 경우 sum<0 조건을 하면 오류가나는걸 생각하지 못함.

class Solution {
public:
    // # mistaken number
    void dfs(TreeNode* root, int sum, vector<int> &tmp, vector<vector<int>> &ret) {
        if (!root) // #1  (sum < 0) -> consider if values are negative?
            return;
        if (sum - root->val == 0 && !root->left && !root->right) {  // #2 only if root has no child,  [1,2] 1 -> answer must be []
            tmp.push_back(root->val);
            ret.push_back(tmp);
            tmp.pop_back(); // #3  must pop at this position
            return;
        }
        tmp.push_back(root->val);
        dfs(root->left, sum - root->val, tmp, ret);
        dfs(root->right, sum - root->val, tmp, ret);
        tmp.pop_back();
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> ret;
        vector<int> tmp;
        dfs(root, targetSum, tmp, ret);
        return ret;
    }
};

그리고 아래와 같이 풀어도 되는데, tmp.push_back(), tmp.pop_back()을 1회만 수행해도 되어 코드가 더 간결해진다. 하지만 개인적으로 로직의 가독성은 조금더 떨어지는듯.

class Solution {
public:
    // # mistaken number
    void dfs(TreeNode* root, int sum, vector<int> &tmp, vector<vector<int>> &ret) {
        if (!root)
            return;
        // remove duplicated tmp push/pop
        tmp.push_back(root->val); // NOTE: this much better.
        if (sum - root->val == 0 && !root->left && !root->right) { 
            //tmp.push_back(root->val); // no need to this
            ret.push_back(tmp);
            //tmp.pop_back(); // no need to this
        } else {
            //tmp.push_back(root->val); // move top
            dfs(root->left, sum - root->val, tmp, ret);
            dfs(root->right, sum - root->val, tmp, ret);
        }
        tmp.pop_back();
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> ret;
        vector<int> tmp;
        dfs(root, targetSum, tmp, ret);
        return ret;
    }
};