一、题目描述

JZ24 二叉树中和为某一值的路径
题目大意：输入一颗二叉树的根节点和一个整数, 按字典序打印出二叉树中节点值的和为输入整数的所有路径. 路径定义为从数的根节点开始往下一直到叶节点形成一条路径.
注意审题：1. 按字典序打印出所有路径 2. 路径一定是从根结点到某个叶子节点的路径

二、算法（深度优先搜索）

解题思路

1. 要求从根到叶子节点的路径, 我们可以想到深度优先搜索, 它可以依次遍历所有的路径, 我们只要在递归时同时维护路径和即可
2. 实现技巧：首先, 为了使递归函数更简洁, 我们可以将用于临时保存路径的数组和结果数组定义为成员; 检查是否满足条件时, 我们不必维护路径和, 而是用目标值减去当前路径和, 最终只需检查目标值是否为0即可

代码实现（C++11）

class Solution {
public:
    vector<vector<int>> ans;    // 结果数组
    vector<int> path;        // 临时路径

    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        dfs(root, expectNumber);
        sort(ans.begin(), ans.end());    // 按字典序排序
        return ans;
    }

    void dfs(TreeNode* root, int target){
        if(!root) return;    // 为空节点返回

        path.push_back(root->val);    // 当前节点入栈
        target -= root->val;    // 减去当前值
        if(root->left == nullptr && root->right == nullptr && target == 0){    // 检查路径和是否满足条件
            ans.push_back(path);
        }
        dfs(root->left, target);    // 向左递归
        dfs(root->right, target);   // 向右递归
        // 回溯
        target += root->val;
        path.pop_back();    
    }
};

时间复杂度：O(n)，n为二叉树的节点数，遍历一次二叉树
空间复杂度：O(n)，递归栈空间和路径数组的空间