C语言求二叉树中和为某一值的路径(三)
- 思路:根据这道题的题意来看,路径可以从每个结点开始,因此首先可以递归所有的的节点,对于每个节点,再递归所有可能的路径。、
- 两层递归的问题。第一层递归遍历所有节点,第二层递归每个节点的路径
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*
* C语言声明定义全局变量请加上static,防止重复定义
*/
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param sum int整型
* @return int整型
*/
static int path_num=0;
//根据节点作为起始,进行递归
int dfs(struct TreeNode *pRoot,int target){
if(pRoot==NULL)
return 0;
if(pRoot->val==target)
path_num++;
dfs(pRoot->left,target-pRoot->val);
dfs(pRoot->right,target-pRoot->val);
return 0;
}
//递归遍历所有节点,每个节点进行递归查询路径
int FindPath(struct TreeNode* root, int sum ) {
//首先递归每个节点
if(root==NULL)
return 0;
//将每个节点都传进去
dfs(root,sum);
FindPath(root->left, sum);
FindPath(root->right, sum);
return path_num;
}