2021-02-12 113. 路径总和 II

题目地址

https://leetcode-cn.com/problems/path-sum-ii/

题目描述

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

思路

1. 先序遍历二叉树，用List记录遍历的节点，遍历到叶子结点时判断路径和是否等于目标值，相等就复制当前路径到结果集中,从叶子结点往回退时将节点移出List，List中始终只有一条路径。

题解

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: vividzcs
 * @Date: 2021/2/12 18:08 下午
 */
public class PathSum {
    public static void main(String[] args) {
        int[] arr = {5,4,8,11,-1,13,4,7,2,-1,-1,5,1};
        NodeTree root = NodeTree.createTree(arr);
        List<List<Integer>> result = new ArrayList<>();
        pathSum(result, root, 22, 0, new ArrayList<>());

        for (int i=0; i<result.size(); i++) {
            for (int j=0; j<result.get(0).size(); j++) {
                System.out.print(result.get(i).get(j) + " ");
            }
            System.out.println();
        }
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.8 MB, 在所有 Java 提交中击败了57.82%的用户
     */
    private static void pathSum(List<List<Integer>> result,
                                               NodeTree root,
                                               int sum,
                                               int currentSum,
                                List<Integer> currentRoad) {
        if (root != null) {
            currentSum += root.getValue();
            currentRoad.add(root.getValue());
            if (sum == currentSum && root.getLeft() == null && root.getRight() == null){
                result.add(copyList(currentRoad));
            }
            pathSum(result, root.getLeft(), sum, currentSum, currentRoad);
            pathSum(result, root.getRight(), sum, currentSum, currentRoad);
            currentRoad.remove(currentRoad.size() - 1);
        }
    }

    private static List<Integer> copyList(List<Integer> currentRoad) {
        List<Integer> result = new ArrayList<>();
        for (int i=0; i<currentRoad.size(); i++) {
            result.add(currentRoad.get(i));
        }
        return result;
    }
}