剑指 Offer 34: 二叉树中和为某一值的路径（一/二）

[songyy5517]

给你二叉树的根节点 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
输出：[]

分析 这道题需要我们找到二叉树中的路径。一个很直接的想法是对二叉树进行先根遍历（DFS），再对所有路径进行验证，保存符合条件的路径。

[songyy5517]

思路：回溯法，递归前序遍历 & 路径记录

1. 异常处理；
2. 定义全局变量，分别记录最终合格的路径，当前路径（LinkedList）以及当前路径之和；
3. DFS遍历二叉树：判断当前节点所在路径是否满足条件： （1）递归出口：当前节点为空时，则返回； （2）将当前节点添加至路径中，并更新路径之和； （3）判断当前路径是否满足条件；若满足，则将当前路径拷贝至结果列表中； （4）继续遍历其左右子节点； （5）路径恢复/回溯：遍历完左右子树后，将当前节点从路径中删除，并恢复路径和。
4. 在主函数中调用递归方法，并返回最终结果路径列表。

复杂度分析

• 时间复杂度： $O(N)$ ，搜索所有的路径需要遍历整颗二叉树，使用 $O(N)$ 大小的时间；
• 空间复杂度： $O(N)$ ，额外定义了 $O(N)$ 大小的变量；最坏情况下，二叉树退化成链表，递归深度最大为 $N$ ，系统使用 $O(N)$ 大小的栈空间。

注意：

1. List可选用LinkedList数据结构
2. 考虑节点值为负数的情况
3. 遍历完当前节点及其子树后，要进行回溯/路径恢复

[songyy5517]

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 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 11:28-11:45
     * 
     * @param root TreeNode类 
     * @param target int整型 
     * @return int整型ArrayList<ArrayList<>>
     */

    ArrayList<ArrayList<Integer>> res = new ArrayList();
    LinkedList<Integer> path = new LinkedList();

    public ArrayList<ArrayList<Integer>> FindPath (TreeNode root, int target) {
        // write code here
        // 思路：二叉树DFS遍历。定义全局变量记录当前路径以及当前和。

        DFS(root, target);
        return res;
    }

    void DFS(TreeNode root, int target){
        // 递归出口
        if (root == null)
            return ;

        // 更新当前路径和当前路径和
        path.add(root.val);
        target -= root.val;    
        // target为0说明当前路径符合要求
        if (target == 0 && root.left == null && root.right == null){
            res.add(new ArrayList<Integer>(path));
        }

        DFS(root.left, target);
        DFS(root.right, target);

        // 回溯
        path.removeLast();
        return;
    }
}

[songyy5517]

2023/1/28 2023/1/30 2024/1/29 2024/2/28

• 回溯操作在执行完递归操作（左节点右节点）后进行；
• 列表的拷贝需要新建列表，而不是直接赋值。

[songyy5517]

JZ84 二叉树中和为某一值的路径(三) 描述 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。

1. 该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
2. 总节点数目为n
3. 保证最后返回的路径个数在整形范围内(即路径个数小于 $2^{31}-1$ )

假如二叉树root为{1,2,3,4,5,4,3,#,#,-1}，sum=6，那么总共如下所示，有3条路径符合要求：

示例1

输入：{1,2,3,4,5,4,3,#,#,-1},6
返回值：3
说明：
如图所示，有3条路径符合      

示例2

输入：{0,1},1
返回值：2

示例3

输入：{1,#,2,#,3},3
返回值：2

[songyy5517]

思路：DFS，嵌套递归

1. 异常处理；
2. 定义递归函数searchPath(TreeNode root, int sum)：搜索以root为根节点的所有路径数；
3. 定义递归方法DFS：遍历二叉树中的所有节点，对每个节点都调用一次seachPath方法；
4. 定义全局变量num记录合格路径总数；
5. 在主函数中调用DFS方法，返回num。

复杂度分析

• 时间复杂度： $O(N^2)$ ，嵌套递归，在遍历节点的同时搜索其对应的路径，使用 $O(N^2)$ 大小的时间；
• 空间复杂度： $O(N)$ ，最坏情况下，二叉树退化成链表，递归深度为 $N$ ，使用 $O(N)$ 大小的栈空间。

[songyy5517]

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 sum int整型 
     * @return int整型
     */
    int num = 0;

    public int FindPath (TreeNode root, int sum) {
        // write code here
        // 思路：DFS。需要注意的是路径的定义，可以不为根节点为首节点。
        // 1. 异常处理
        if (root == null)
            return 0;

        // 2. DFS
        dfs(root, sum);

        return num;
    }

    // 查找以root为根节点的合格路径数
    void searchPath(TreeNode root, int sum){
        // 递归出口
        if (root == null)
            return;

        // 满足条件
        if (sum == root.val)
            num ++;

        searchPath(root.left, sum - root.val);
        searchPath(root.right, sum - root.val);
    }

    // 遍历树中的各个节点
    void dfs(TreeNode root, int sum){
        // 递归出口
        if (root == null)
            return ;

        // 以当前节点为根，查找合格路径
        searchPath(root, sum);

        dfs(root.left, sum);    
        dfs(root.right, sum);
    }
}