剑指offer(C++)-JZ34：二叉树中和为某一值的路径(二)(数据结构-树)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

如二叉树root为{10,5,12,4,7},expectNumber为22

则合法路径有[[10,5,7],[10,12]]

数据范围:

树中节点总数在范围 [0, 5000] 内

-1000 <= 节点值 <= 1000

-1000 <= expectNumber <= 1000

示例1：

输入：

{10,5,12,4,7},22

返回值：

[[10,5,7],[10,12]]

说明：

返回[[10,12],[10,5,7]]也是对的 

示例2： 

输入：

{10,5,12,4,7},15

返回值：

[]

解题思路：

本题考察数据结构树的使用，运用深度优先遍历dfs解题。

1）定义result存储结果，定义path获取路径信息。

2）dfs函数中，path存储当前结点的值，若当前结点符合目标值且无左右子树，则说明该path是我们要的，存储到result中。

3）第二步如果没得到目标path，则继续对结点的左子树进行dfs，再对右子树进行dfs，注意此时输入给dfs的expectNumber是减去了当前结点数值的。

4）dfs执行完左右子树的判断后，务必进行pop_back处理，将最后一个结点弹出，因为该路径失败了，溯回找上一个分叉路口，走另一条分支，以此类推。

测试代码：

/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
    // 深度遍历
    void dfs(TreeNode* root,int expectNumber,vector<int> &path,vector<vector<int>> &result)
    {
        path.push_back(root->val);
        if(root->val==expectNumber&&!root->left&&!root->right)
            result.push_back(path);
        if(root->left)
            dfs(root->left,expectNumber-root->val,path,result);
        if(root->right)
            dfs(root->right,expectNumber-root->val,path,result);
        path.pop_back();
    }
    
    vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> result;
        vector<int> path;
        if(!root)
            return result;
        dfs(root,expectNumber,path,result);
        return result;
    }
};