题解 | #牛牛的路径总和#【Java】

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 targetSum int整型
     * @return int整型二维数组
     */
    public int[][] findPaths(TreeNode root, int targetSum) {
        List<List<Integer>> paths = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        findPathsHelper(root, targetSum, paths, currentPath);
	  // 集合转二维数组返回,返回符合条件的所有路径
        int[][] result = new int[paths.size()][];
        for (int i = 0; i < paths.size(); i++) {
            int[] path = new int[paths.get(i).size()];
            for (int j = 0; j < paths.get(i).size(); j++) {
                path[j] = paths.get(i).get(j);
            }
            result[i] = path;
        }
        return result;
    }
	// 用来寻找路径的功能函数，递归主分支和左右子树，然后回溯，主要思想。
    private void findPathsHelper(TreeNode root, int targetSum,
                                 List<List<Integer>> paths, List<Integer> currentPath) {
        if (root == null) {
            return;
        }
        currentPath.add(root.val);
        if (root.left == null && root.right == null && root.val == targetSum) {
            paths.add(new ArrayList<>(currentPath));
        }
        findPathsHelper(root.left, targetSum - root.val, paths, currentPath);
        findPathsHelper(root.right, targetSum - root.val, paths, currentPath);
        currentPath.remove(currentPath.size() - 1);
    }
}

本题知识点分析：

1.二叉树

2.前序遍历

3.深度优先搜索DFS

4.递归

5.回溯

6.数组遍历

7.集合转数组

本题解题思路分析：

1.看着知识点多，但只要会拆分函数，就会比较简单

2.findPathsHelper用来寻找所有符合条件的路径，主要思想是：前序遍历获取该结点的值，存放currentPath这个集合

3.如果某点路径已经走到底，这时候root.left和right都等于null,如果此时又符合条件，满足路径和等于targetSum,那么添加到集合Paths中，其实可以写个全局变量，这里我用的传参，无所谓了，引用类型反正传递的是地址

4.分别遍历左右子树，记得将需要的targetSum-当前的节点值root.val

5.经典回溯，在递归左右子树后，需要将自身节点的值去掉 currentPath.remove(currentPath.size() - 1);

关键：回溯保证了算法能够正确的找出所有满足条件的路径，而不是只找到其中一条路径。

本题使用编程语言: Java

如果对你有帮助，可以点个赞捏，感谢~