题目

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

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > results;
        vector<int> one;
        if(!root) return results;
        DFS(one,expectNumber,0,root,results);
		return results;
    }
    void DFS(vector<int>& one,int expect,int sum,TreeNode* node,vector<vector<int> >& results)
    {
        one.push_back(node->val);
        sum = sum+node->val;
        if(node->left==NULL&&node->right==NULL&&sum == expect)
        {
            results.push_back(one);
        }
        if(node->left)
        {
            DFS(one,expect,sum,node->left,results);
        }
        if(node->right)
        {
            DFS(one,expect,sum,node->right,results);
        }
        one.pop_back();
        return ;
    }
}；

思路

使用DFS,一定要记住首先判断根结点，要不然牛客上一直报错（段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起）。

其他就是一个DFS解决就好了。