内容摘要：Leetcode : https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof“GitHu

Leetcode : https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof

“GitHub : https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_27_pathSum/Solution.java

二叉树中和为某一值的叉树路径

“题目描述 ：给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的中和值路径。难度：中等叶子节点 是为某指没有子节点的节点。示例 1：

输入：root = [5,叉树4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]] 

示例 2：

输入：root = [1,2,3], targetSum = 5 输出：[] 

示例 3：

输入：root = [1,2], targetSum = 0 输出：[] 

解题思路：

“本问题是典型的二叉树方案搜索问题，使用回溯法解决，中和值其包含 先序遍历 + 路径记录 两部分。为某

先序遍历： 按照 “根、叉树左、中和值右” 的为某顺序，服务器托管遍历树的叉树所有节点。 路径记录： 在先序遍历中，中和值记录从根节点到当前节点的为某路径。当路径为 ① 根节点到叶节点形成的叉树路径 且 ② 各节点值的和等于目标值 sum 时，将此路径加入结果列表。中和值

算法流程：pathSum(root，为某sum) 函数:

初始化：结果列表res，路径列表 path. 返回值：返回res即可。

recur (root, tar) 函数:

递推参数：当前节点root，当前目标值tar 。 终止条件：若节点root为空，则直接返回。源码库 递推工作： 路径更新：将当前节点值root. val加入路径path ; 目标值更新：tar=tar - root.val(即目标值tar从sum减至0); 路径记录：当①root为叶节点且②路径和等于目标值，则将此路径path加入res。 先序遍历：递归左1右子节点。 路径恢复：向上回溯前，需要将当前节点从路径path中删除，即执行path. pop()。

复杂度分析：

时间复杂度 O(N)： N 为二叉树的节点数，先序遍历需要遍历所有节点。 空间复杂度 O(N)： 最差情况下，即树退化为链表时，path 存储所有树节点，使用 O(N) 额外空间。 package com.nateshao.sword_offer.topic_27_pathSum; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; /**  * @date Created by 邵桐杰 on 2021/12/1 16:45  * @微信公众号 程序员千羽  * @个人网站 www.nateshao.cn  * @博客 https://nateshao.gitee.io  * @GitHub https://github.com/nateshao  * @Gitee https://gitee.com/nateshao  * Description: 二叉树中和为某一值的路径  */ public class Solution {      public static void main(String[] args) {          TreeNode node1 = new TreeNode(10);         TreeNode node2 = new TreeNode(5);         TreeNode node3 = new TreeNode(12);         TreeNode node4 = new TreeNode(4);         TreeNode node5 = new TreeNode(7);         node1.left = node2;         node1.right = node3;         node2.left = node4;         node2.right = node5;         Solution p = new Solution();         System.out.println(p.listAll);         p.pathSum(node1, 22);         for (List<Integer> list : p.listAll) {              for (int i : list) {                  System.out.print(i + " ");             }             System.out.println();         }         /**          * []          * 10 5 7          * 10 12          */     }     /