题解 | #二叉树中和为某一值的路径(三)#
二叉树中和为某一值的路径(三)
http://www.nowcoder.com/practice/965fef32cae14a17a8e86c76ffe3131f
思路：每次将原树中遇到的节点作为子树的根节点送入dfs函数中查找有无路径，如果该节点为空则返回。 然后递归遍历这棵树每个节点，每个节点都需要这样操作。 在dfs函数中，也是往下递归，遇到一个节点就将sum减去节点值再往下。 剩余的sum等于当前节点值则找到一种情况。
代码实现：
public class Solution {
private int res = 0;
//dfs查询以某结点为根的路径数
private void dfs(TreeNode root, int sum){
if(root == null)
return;
//符合目标值
if(sum == root.val)
res++;
//进入子节点继续找
dfs(root.left, sum - root.val);
dfs(root.right, sum - root.val);
}
//dfs 以每个结点作为根查询路径
public int FindPath (TreeNode root, int sum) {
//为空则返回
if(root == null)
return res;
//查询以某结点为根的路径数
dfs(root, sum);
//以其子结点为新根
FindPath(root.left, sum);
FindPath(root.right, sum);
return res;
}
}
查看3道真题和解析