1 题目

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/path-sum-iii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2 Java

2.1 方法一（回溯，非模板；这个不好）

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int pathSum(TreeNode root, int sum) { helper(root, sum); return res; } List<Integer> list = new ArrayList<>(); int res = 0; public void helper(TreeNode root, int sum) { // if 是否遍历到底 if(root == null) return; // if 路径是否为解 int tmp = 0; list.add(root.val); for(int i = list.size() - 1; i >= 0; i--){ tmp += list.get(i); if(tmp == sum) res++; } // for 多路选择 helper(root.left, sum); helper(root.right, sum); // 撤销选择 list.remove(list.size() - 1); } }

2.2 方法二（回溯，模板）

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int pathSum(TreeNode root, int sum) { // 特殊情况 if(root == null) return 0; // 先将根节点加入list，再进入递归 list.add(root.val); helper(root, sum); return res; } List<Integer> list = new ArrayList<>(); int res = 0; public void helper(TreeNode root, int sum) { // if 路径是否为解 int tmp = 0; for(int i = list.size() - 1; i >= 0; i--){ tmp += list.get(i); if(tmp == sum) res++; } // for 多路选择 if(root.left != null){ // 做选择 list.add(root.left.val); helper(root.left, sum); // 撤销选择 list.remove(list.size() - 1); } if(root.right != null){ // 做选择 list.add(root.right.val); helper(root.right, sum); // 撤销选择 list.remove(list.size() - 1); } } }

3 二刷

3.1 方法一（回溯递归，本层操作本层做）

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int pathSum(TreeNode root, int sum) { helper(root, sum); return res; } int res = 0; List<Integer> list = new ArrayList<>(); public void helper(TreeNode root, int sum) { // if出口 if(root == null) return; // 做选择 list.add(root.val); // if判断，路径是否为解 // ！！！以当前节点为末节点，向上寻找，看是否存在满足条件的路径 int tmpSum = 0; for(int i = list.size() - 1; i >= 0; i--){ tmpSum += list.get(i); if(tmpSum == sum) res++; } // for 多路选择 helper(root.left, sum); helper(root.right, sum); // 撤销选择 list.remove(list.size() - 1); } }