描述

这是一篇针对初学者的题解，用递归方法实现。
知识点：树，递归
难度：一星

题解

题目抽象：给定一颗二叉树，找出满足从根节点到叶子节点和为sun的所有路径。
如图：

方法：递归

前置知识：

1. 首先清楚叶子的表示：如果节点为root, 那么当前节点为叶子节点的必要条件为!root->left && !root->right

2. 找出路径，当然需要遍历整棵树，这里采用先序遍历，即：根节点，左子树，右子树
   代码如下：

   void preOrder(TreeNode *root) {
    // process root
   
    if (root->left) preOrder(root->left);
    if (root->right) preOrder(root->right);
   }

具备了上面两个前置知识后，这里无非增加了路径和sum 和 叶子节点的判断。
递归算法三部曲：

1. 明白递归函数的功能：FindPath(TreeNode* root,int sum)，从root节点出发，找和为sum的路径
2. 递归终止条件：当root节点为叶子节点并且sum==root->val, 表示找到了一条符合条件的路径
3. 下一次递归：如果左子树不空，递归左子树FindPath(root->left, sum - root->val),如果右子树不空，递归右子树，FindPath(root->right, sum - root->val)

但是，你可能会问，这里没有保存路径啊？是的，可以用两个全局变量vector<int> path, vector<vector<int>> ret来保存
代码中用了引用，将全局变量作为函数参数来进行全局传递。

代码

class Solution {
public:
    using vvi = vector<vector<int>>;
    using vi = vector<int>;
    void dfs(TreeNode *root, int sum, vi &path, vvi &ret) {
        path.push_back(root->val);
        if (sum == root->val && !root->left && !root->right) {
            ret.push_back(path);
        }
        if (root->left) dfs(root->left, sum - root->val, path, ret);
        if (root->right) dfs(root->right, sum - root->val, path, ret);
        path.pop_back(); // 代码走到这里，表明要回溯，代表当前path中的root节点我已经不需要了
    }
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vvi ret;
        vi path;
        if (!root) return ret;
        dfs(root, expectNumber, ans, ret);
        return ret;
    }
};

时间复杂度：O(n), 树的所有节点需要遍历一次
空间复杂度：O(n), 当树退化到链表时，递归空间为O(n)