113. Path Sum II

題目網址：https://leetcode.cn/problems/path-sum-ii/

題意：給一 BT 的 root 和一整數 targetSum, 返回所有 root-to-leaf 之路徑總和為 targetSum 的 path。

Solution 1：

想法：利用 DFS + Backtracking

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root, targetSum);
        return res;
    }

private:
    vector<int> cur;
    vector<vector<int>> res;

    void dfs(TreeNode* root, int targetSum){
        if (!root) {
            return;
        }

        // 若為 leaf node
        if (!root->left && !root->right) {
            if (root->val == targetSum) {
                cur.emplace_back(root->val);
                res.emplace_back(cur);
                cur.pop_back(); // 返回上一步時要拿掉當前 node
            }
            return;
        }

        // 不為 leaf node
        cur.emplace_back(root->val);
        dfs(root->left, targetSum - root->val);
        dfs(root->right, targetSum - root->val);
        cur.pop_back(); // 返回上一步時要拿掉當前 node
    }
};

• time：$O(n)$ ➔ 遍歷整個 BT
• space：$O(n)$ ➔ 遞迴深度不超過 n

Solution 2：

想法：利用 BFS, 概念同 112. Path Sum, 只是要用 parent 紀錄每個 node 的 parent, 這樣找到符合的 path 時, 才能得到一條從 leaf to root 的 path, 將其反轉過後便是 root to leaf 的 path

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if (!root) {
            return res;
        }

        using pti = pair<TreeNode*, int>;
        queue<pti> q;
        q.emplace(pti{root, 0}); // sum 初始設 0, 而非 root->val, 因為等等會加上 root->val

        while (!q.empty()) {
            const auto front = q.front();
            q.pop();

            TreeNode* curNode = front.first;
            const int curSum = front.second + curNode->val;

            // 若為 leaf
            if (!curNode->left && !curNode->right) {
                if (curSum == targetSum) {
                    // curNode 的 parent 必不為 leaf, 故 curNode 的 parent 已被記錄
                    getPath(curNode);
                }
            } else {
                if (curNode->left) {
                    parent[curNode->left] = curNode; // 紀錄 child 的 parent
                    q.emplace(pti{curNode->left, curSum});
                }

                if (curNode->right) {
                    parent[curNode->right] = curNode; // 紀錄 child 的 parent
                    q.emplace(pti{curNode->right, curSum});
                }
            }
        }

        return res;
    }

private:
    vector<vector<int>> res;
    unordered_map<TreeNode*, TreeNode*> parent; // {cur_node : parent}

    void getPath(TreeNode* node){
        vector<int> path;

        // get path from leaf to root
        while (node) {
            path.emplace_back(node->val);
            node = parent[node];
        }

        reverse(path.begin(), path.end()); // get path from root to leaf
        res.emplace_back(path);
    }
};

• time：$O(n)$ ➔ 遍歷整個 BT
• space：$O(n)$ ➔ q 和 parent 的元素不超過 n