字节-LeetCode【面试题34.二叉树中和为某一值的路径】

class Solution {

    private List<List<Integer>> pathList = new ArrayList<>();
    private int sum = 0;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<TreeNode> tmpList = new ArrayList<>();
        dfsTree(root, target, tmpList);
        return pathList;
    }

    private void dfsTree(TreeNode root, int target, List<TreeNode> tmpList) {
        if (root == null) {
            return;
        }

        // 必须遍历到最底层的子节点，才算一条路径结束。此时再判断整个路径之和是否等于目标值
        if (root.left == null && root.right == null) {
            if (sum + root.val == target) {
                copyValue(tmpList, root);
                return;
            }
        } else {
            // 不等于，则继续遍历
            tmpList.add(root);
        }
        // 此处容易错过
        sum += root.val;

        // 先遍历左子树
        dfsTree(root.left, target, tmpList);
        // 再遍历右子树
        dfsTree(root.right, target, tmpList);
        // 左右子树都遍历完，就移除当前节点，递归到父节点，并减去当前值
        tmpList.remove(root);
        sum -= root.val;
    }

    private void copyValue(List<TreeNode> tmpList, TreeNode root) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < tmpList.size(); i++) {
            list.add(tmpList.get(i).val);
        }
        list.add(root.val);
        pathList.add(list);
    }
}