剑指offer 24 二叉树中和为某一值的路径 ★★★★

题目描述

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

这类问题可以用带记忆的DFS来解决。分享一个这类问题的典型解法。
class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> ret;                   //记录所有的路径
        vector<int> trace;               //一个路径
        if(root)               //如果根节点不为空，进行dfs遍历
            dfs(root,expectNumber,ret,trace);
        return ret;
    }
    void dfs(TreeNode* root,int s,vector<vector<int>> &ret,vector<int> &trace) {
        trace.push_back(root->val);   //将当前根节点的值，加入trace
        if(!root->left&&!root->right) {    //是叶节点,进入if语句
            if(s==root->val)//判断，s是否等于叶节点的值
                ret.push_back(trace);
        }
        if(root->left)
            dfs(root->left,s-root->val,ret,trace);
        if(root->right)
            dfs(root->right,s-root->val,ret,trace);
        trace.pop_back();
    }
};

链接：https://www./questionTerminal/b736e784e3e34731af99065031301bca
来源：牛客网

/* 思路更为清晰的递归方式 -- path与ret均定义在函数内部 */
/* 递归方式 */
class Solution {
    void DFSFindPath(TreeNode* root, int rest, vector<vector<int>> &path, vector<int> &ret)
    {
        rest -= root->val;  // 减去当前结点的值
        ret.push_back(root->val);
         
        // 如果是叶子结点，则看此时路径和是否等于exceptNumber，是则保留该路径
        if(root->left == nullptr && root->right == nullptr)
            if(rest == 0) path.push_back(ret);
         
        // 如果不是叶子结点，若rest != 0,则递归进入左右子树（注：若rest==0，则删除该结点后返回）
        if( rest != 0 && root->left != nullptr)
            DFSFindPath(root->left,rest,path,ret);
        if( rest != 0 && root->right != nullptr)
            DFSFindPath(root->right,rest,path,ret);
         
        ret.pop_back();   // 退出该结点前，在路径中删除该结点     
    }
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) 
    {
        vector<vector<int>> path;
        vector<int> ret;
        if(root != nullptr)
            DFSFindPath(root,expectNumber,path,ret);
         
        return path;
    }
};