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

题目

给定一个二叉树root和一个整数值 sum 
  
  
  
  
  
  
  
 ，求该树有多少路径的的节点值之和等于 sum                 。 1.该题路径定义不需要从根节点开始  
  
  
  
  
  
  
  ，也不需要在叶子节点结束
 


 


 


 


 


 


 


 

，但是一定是从父亲节点往下到孩子节点 2.总节点数目为n 3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)

方法 非递归层次遍历

思路

算法实现

既然要找所有路径上节点和等于目标值的路径个数
 
 
 
 
 
 
 
，那我们肯定先找这样的路径起点啊   
   
   
   
   
   
   
   ，但是我们不知道起点究竟在哪里
 

 

 

 

 

 

 

 
， 而且任意节点都有可能是起点

 

 

 

 

 

 

 

，那我们就前序遍历二叉树的所有节点                ，每个节点都可以作为一次起点
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 ，即子树的根节点
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
。 具体做法： step 1：每次将原树中遇到的节点作为子树的根节点送入dfs函数中查找有无路径















，如果该节点为空则返回














。 step 2：然后递归遍历这棵树每个节点                       ，每个节点都需要这样操作 
  
  
  
  
  
  
  
 。 step 3：在dfs函数中 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，也是往下递归























，遇到一个节点就将sum减去节点值再往下
  
  
  
  
  
  
  
 。 step 4：剩余的sum等于当前节点值则找到一种情况
 


 


 


 


 


 


 


 
。

代码

package mid.JZ84二叉树中和为某一值的路径3; import java.util.*; 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整型 */ private int res = 0; public int FindPath(TreeNode root, int sum) { // write code here if (root == null) return res; //查询以某结点为根的路径数 dfs(root, sum); //以其子结点为新根 FindPath(root.left, sum); FindPath(root.right, sum); return res; } public void dfs (TreeNode root, int sum) { if (root == null) return; //符合目标 
 
 
 
 
 
 
 
。res++ if (sum == root.val) res++; //子节点继续查找 dfs(root.left, sum - root.val); dfs(root.right, sum - root.val); } }