Leetcode 113:路径总和II

1. 题目描述

2. 解题思路：

        这道题其实应该结合 112：路径总和I 来看。

        路径总和I：找从根节点到叶子节点的所有路径和有没有等于 target 的路径，如果有，则返回  true，没有返回 false。路径总和II：输出从根节点到叶子节点的路径和等于 target 的全部路径。 它们的思路大体是一样的。

即当到达叶子结点时（左右子树均为空），判断此时路径和是否等于 target，等于则输出；当遇到非空非叶子节点时，先将其加入路径，之后递归左右子树，递归结束时，再将节点从路径中删除。

在这段描述中，我们用到的数据结构有：用来记录路径的 path数组、用来存放所有合理路径的res数组。

3. 代码实现

class Solution {
public:
        vector< vector > res;
        vectorpath;
    void helper(TreeNode *root,int targetSum){
        if(!root)
            return;
        path.push_back(root->val);
        if(!root->left&&!root->right){
            if(targetSum==root->val){
                res.emplace_back(path); //emplace_back 函数，用于将path加入res
            }
        }
        helper(root->left,targetSum-root->val);
        helper(root->right,targetSum-root->val);
        path.pop_back();
    }
    vector> pathSum(TreeNode* root, int targetSum) {
        if(!root)
            return res;
        helper(root,targetSum);
        return res;
    }
};

4. 一些小tips

• 一定要找好递归出口，不然乱用空指针会报执行出错哦。
• 树、图这块时用到递归最多的地方，这就要求我们不仅要理解递归的思想，跟着递归程序一步一步走，而且要足够熟悉相关数据结构~  说不定我再勤奋一点也能出个归纳呢啊哈哈哈