题解 | #二叉树中和为某一值的路径(二)#

思路:递归+回溯；二叉树和为某一值的所有路径，使用这个target减去当前节点的值，然后比较递归左右孩子，递归出口设置为左右孩子均为空，然后判断此时是否和target的值相等。否则回溯。

重点：重点是使用数组+静态变量 记录递归的路径，当满足条件时，将路径拷贝到返回结果中。

返回值：容易迷惑的还是返回值，第一个是returnSize记录路径的总数；第二个是 returnColumnSizes，记录每一条路径的深度，值得注意的是这个参数是二重指针，第一步应该先初始化，也就是指向整数指针的指针，使用malloc初始化为100个指针，（*returnColumnSizes)[0~100]分别指向每一条路径的深度。

Step1:

 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param target int整型 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
static int sum[5000];	//一个静态数组 记录当前路径值
static int top = 0;		//静态数组的top指针 指向数组的顶部

static int ans_top = 0;		//这个是路径数组的顶部指针，记录是第几条路径
static int column[20];		//记录每条路径的深度，搭配ans_top使用

int AllPath(struct TreeNode* root, int target,int ** ans) {
//递归出口，空指针返回
	if (root == NULL) {
		return 0;
	}
    //当前节点值存入路径数组
	sum[top++] = root->val;
    //叶子节点，可以判断路径是否满足了
	if (root->left == NULL && root->right == NULL) {
    //路径满足，将路径记录下来
		if (root->val == target) {
        //路径拷贝到ans[]中
			ans[ans_top] = (int*)malloc(sizeof(int) * top);
			memcpy(ans[ans_top], sum, top*(sizeof(int)));
            //记录深度
			column[ans_top++] = top;
		}
        //舍弃掉这个叶子值 top--
		top--;
		return 0;
		
	}
	
	//递归左子树
	AllPath(root->left,target-root->val,ans);
    //递归右子树
	AllPath(root->right, target - root->val,ans);
    //左右子树递归完成。数组路径回退一步。
	top--;
	return 0;

}
int** FindPath(struct TreeNode* root, int target, int* returnSize, int** returnColumnSizes ) {
    int** ans= (int**)malloc(sizeof(int*) * 100);
    AllPath(root, target,ans);
	*returnSize = ans_top;
	*returnColumnSizes = (int*)malloc(sizeof(int) * ans_top);
    //复制到returnColumnSizes
	for (int i = 0; i < ans_top; i++) {
		(* returnColumnSizes)[i] = column[i];
	}
	return ans;
}