题解 | #二叉树中和为某一值的路径(三)#二次递归解决问题
二叉树中和为某一值的路径(三)
https://www.nowcoder.com/practice/965fef32cae14a17a8e86c76ffe3131f
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 { int res = 0; /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @param sum int整型 * @return int整型 */ public int FindPath (TreeNode root, int sum) { dfs(root, sum); return res; } // 按照先序遍历次序遍历二叉树,根->左->右 public void dfs(TreeNode root, int sum) { if (root == null) { return; } // 计算本层的节点下的值 calculate(root, sum, 0); // 遍历左子树 dfs(root.left, sum); // 遍历右子树 dfs(root.right, sum); } // 计算当前节点以下的节点相加后是否等于sum // 这里实际上只会算例如二叉树为{1,2,3,4,5,4,3,#,#,-1} // 如果当前是root->1,只会算1->2->4 , 1->2->5->-1 , 1->3->4 , 1->3->3 // 假设当前节点是2,只会算 2->4 ,2->5->-1 public void calculate(TreeNode root, int sum, int temp) { if (root == null) { return; } temp += root.val; if (sum == temp) { res++; } calculate(root.left, sum, temp); calculate(root.right, sum, temp); } }