深度优先搜索

题目： 二叉树中和为某一值的路径

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

样例：
给出二叉树如下所示，并给出num=22。

   	   5
 	 /   \
	4     6
   /     / \
  12    13  6
 / \       / \
9   1     5   1

输出：[[5,4,12,1],[5,6,6,5]]

思路： 这是一道典型的深度优先搜索问题，从根节点一直搜索到叶子节点，如果和是num，添加到二维数组里面，直到遍历完整棵树

class Solution {
public:
// 	int sum;
	vector<vector<int>> res;
	vector<int> path;
    vector<vector<int>> findPath(TreeNode* root, int sum) {
    // 	sum = sum;
        dfs(root,sum);
        return res;
    }
    void dfs(TreeNode* root,int sum)
    {
        using namespace std;
    	//如果一输入进来的root为null,就返回findPath函数
    	if(!root) return;
    	cout << sum << endl;
    	path.push_back(root->val);
    	sum = sum - root->val;
    	if(!root->left&&!root->right&&!sum) res.push_back(path);
    	if(root->left) dfs(root->left,sum);
    	cout << sum << endl;
    	if(root->right) dfs(root->right,sum);
    	cout << sum << endl;
    	path.pop_back();
    }
};

递归调用的原理： 主调函数调用被调函数，一直递归，直到边界返回主调函数

这里的int sum是类成员变量，但是由于函数形参也定义了int sum，所以进了函数体会，默认为局部的形参。但是如果将类成员变量换为int s; s = sum ; s = sum - root -> val，则会出错，因为类成员变量的值是不会因为返回主调函数而发生变化的。涉及到不同变量的存储位置问题。

cout << sum << endl; 是为了搞清楚递归调用的测试代码

测试输入
[10, 9, null, 10, null, null, null]
29

测试输出
29
19
10
0
0
10
10
19
19
[[10, 9, 10]]