【数据结构和算法实践-树-LeetCode113-路径总和Ⅱ】

数据结构和算法实践-树-LeetCode113-路径总和Ⅱ

• • 题目
  • My Thought
  • 代码示例
  • • JAVA-8

题目

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

My Thought

题目限定的条件为是否存在到叶子节点的路径总和与目标相等：
一、参考之前的路径总和
二、需要注意的是，每个节点其实要回退到node的，不然会无限扩展
然后再进行递归，递归要注意两个方面：
一、自我调用
二、终止条件：即函数边界
注意点：树、递归

代码示例

JAVA-8

    static List<List<Integer>> resultAll = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> processList = new ArrayList<>();
        if (root == null) {
            return result;
        }
        if(resultAll != null){
            resultAll.clear();
        }
        process(root, 0, targetSum, processList);
        return resultAll;
    }

    private static void process(TreeNode node, int preSum, int targetSum, List<Integer> processList) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            if (node.val + preSum == targetSum) {
                processList.add(node.val);
                List<Integer> resultList = new ArrayList<>();
                for (Integer n : processList) {
                    resultList.add(n);
                }
                resultAll.add(resultList);
                processList.remove(processList.size() - 1);
            }
        }
        processList.add(node.val);
        preSum += node.val;
        process(node.left, preSum, targetSum, processList);
        process(node.right, preSum, targetSum, processList);
        processList.remove(processList.size() - 1);
    }