LeetCode 113—— 路径总和 II

1. 题目

2. 解题思路

看到树的问题一般我们先考虑一下是否能用递归来做。

假设 root 节点的值为 value，如果根节点的左子树有一个路径总和等于 targetSum - value，那么只需要将根节点的值插入到这个路径列表中作为第一个元素即可。同理，右子树也是一样。

最后，我们只需要特别处理一下边界条件即可：

• 如果树是空的，那么直接返回一个空的列表。

• 如果到达了叶子结点，而且叶子结点的值等于 targetSum，那么就返回一个包含叶子结点值的列表。

3. 代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int> > ret;
        if (root == nullptr) {
            return ret;
        }
        if (root->left == nullptr && root->right == nullptr && root->val == targetSum) {
            vector<int> a(1, targetSum);
            ret.push_back(a);
            return ret;
        }
        vector<vector<int> > left_res = pathSum(root->left, targetSum-root->val);
        vector<vector<int> > right_res = pathSum(root->right, targetSum-root->val);
        for (size_t i = 0; i < left_res.size(); ++i) {
            left_res[i].insert(left_res[i].begin(), root->val);
            ret.push_back(left_res[i]);
        }
        for (size_t i = 0; i < right_res.size(); ++i) {
            right_res[i].insert(right_res[i].begin(), root->val);
            ret.push_back(right_res[i]);
        }
        return ret;
    }
};

上面代码的实现思路比较好理解，但是 insert 比较耗时，能不能直接 push_back 呢？

我们定义一个 path，访问到某一个节点后，就把这个节点的值添加到 path 中去，然后再分别递归调用左子树和右子树，只不过我们这里传入一个 path 的引用，当访问到叶子结点并且叶子结点的值刚好等于 targetSum，这时候的 path 刚好是一个满足条件的路径，我们把它放入到结果中去。

然后，把当前节点的值 pop_back 出去，回到上一级节点继续搜索其它路径。

class Solution {
public:
    vector<vector<int> > ret;

    void dfs(TreeNode* root, int targetSum, vector<int>& path) {
        if (root == nullptr) {
            return;
        }
        path.emplace_back(root->val);
        if (root->left == nullptr && root->right == nullptr && root->val == targetSum) {
            ret.emplace_back(path);
        }
        dfs(root->left, targetSum-root->val, path);
        dfs(root->right, targetSum-root->val, path);
        path.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        dfs(root, targetSum, path);
        return ret;
    }
};