代码随想录——二叉树17-路径总和

这两道题目对于递归函数的返回值是不同的，这里进行总结，二叉树遍历中递归函数返回值何时有何时没有。

这里总结如下三点：

1. 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是路径总和ii）

2. 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先中介绍）

3. 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（路径总和i的情况）

代码
路径总和

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        //显然用递归
        if(root == nullptr)return false;
        targetSum -= root->val;
        if(root->left == nullptr && root->right == nullptr ){//叶子
            if(targetSum == 0)return true;
            else return false;
        }
        return hasPathSum(root->left,targetSum) || hasPathSum(root->right,targetSum);

    }
};

路径总和ii

class Solution {
public:
    void traversal(TreeNode* cur,int targetsum,vector<int> path,vector<vector<int>>& ans){
        if(cur == nullptr)return;
        targetsum -= cur->val;
        path.emplace_back(cur->val);
        if(cur->left == nullptr && cur->right == nullptr && targetsum == 0){
            ans.emplace_back(path);
            return;
        }
        if(cur->left){
            traversal(cur->left,targetsum,path,ans);
        }
        if(cur->right){
            traversal(cur->right,targetsum,path,ans);
        }

    }

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