题解 | #二叉树中和为某一值的路径(三)#
二叉树中和为某一值的路径(三)
https://www.nowcoder.com/practice/965fef32cae14a17a8e86c76ffe3131f
解答：看到所有字眼，立即思考双递归，其中一个递归遍历所有节点，一个递归求解逻辑。根据题意路径只能是父亲往下，则往下找就ok，但需要注意一个问题就是一般问题写习惯了找到以后习惯性return，而这题不能return，因为可能两条路径某些节点完全重合，即该条路径终点如果不是叶子节点，则继续往下可能还有满足条件的路径。时间复杂度O(n^2),空间复杂度O(1)。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param sum int整型
* @return int整型
*/
int res=0;
int FindPath(TreeNode* root, int sum) {
// write code here
if(root==NULL)return 0;
dfs(root,sum);
return res;
}
void dfs(TreeNode* root,int tar){
if(root==NULL)return;
dfs_in(root,0,tar);
dfs(root->left,tar);
dfs(root->right,tar);
}
void dfs_in(TreeNode* root,int k,int tar){
if(root==NULL)return;
k=k+root->val;
if(k==tar){
res++;
}
dfs_in(root->left,k,tar);
dfs_in(root->right,k,tar);
}
};
腾讯公司福利 867人发布
