剑指offer19 JZ84 二叉树中和为某一值的路径(三)

1. 题目要求不一定从根节点出发到子节点结束，只是父子节点满足要求即可

思路

• 既然要找所有路径上节点和等于目标值的路径个数，那我们肯定先找这样的路径起点，但是我们不知道起点究竟在哪里，而且任意节点都有可能是起点，那我们就前序遍历二叉树的所有节点，每个节点都可以作为一次起点，即子树的根节点。

//以其子结点为新根
FindPath(root.left, sum); 
FindPath(root.right, sum);

• 查找路径的时候呢，也需要往下遍历，因此还可以继续前序遍历该子树，在遍历的过程遇到一个节点，sum相应减少，若是到最后往下的一个节点值正好等于剩下的sum，则找到一种情况。

//符合目标值
if(sum == root.val) 
    res++;

• 因为前序递归的次序是根左右，因此一定是往下找的路径，不会往上回溯。

//进入子节点继续找
dfs(root.left, sum - root.val); 
dfs(root.right, sum - root.val);

具体做法

• step 1：每次将原树中遇到的节点作为子树的根节点送入dfs函数中查找有无路径，如果该节点为空则返回。
• step 2：然后递归遍历这棵树每个节点，每个节点都需要这样操作。
• step 3：在dfs函数中，也是往下递归，遇到一个节点就将sum减去节点值再往下。
• step 4：剩余的sum等于当前节点值则找到一种情况。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
   
    public void dfs(TreeNode node,int sum){
        if(node==null){
            return ;
        }
        //剩余值等于当前值 此时已经找到了一条，说明当前值想减为0了
        if(sum==node.val){
            res++;
        }
        //前序遍历 递归向下 寻找子节点
        dfs(node.left,sum-node.val);
        dfs(node.right,sum-node.val);
    }
     int res=0;//记录答案
    public int FindPath (TreeNode root, int sum) {
        if(root==null){
            return 0;
        }
        //查询以某节点为根
        dfs(root,sum);
         //子节点为根
        // write code here
         FindPath (root.left, sum) ;
        FindPath(root.right,sum);
       return res;
    }
}