题解 | 二叉树根节点到叶子节点和为指定值的路径

分析

注意到本题的要求是，找到所有满足从(根节点)到某个(叶子节)经过的路径上的节点之和等于目标和的路径。核心思想是对树进行一次遍历，在遍历时记录从根节点到当前节点的路径和，以防止重复计算.

解法一：深度优先搜索(DFS)

思路步骤：

• 该递归一共分为两层

  • 第一层：pathSum(TreeNode root, int sum)，可以理解为路径的起点从哪开始
  • 第二层：helper(TreeNode root, int sum)，在该起点下合法路径的数量
  • 因为整个递归是从上到下的dfs，所以不存在路径重复计算的问题

• 枚举每一条从root节点到叶子节点的路径

• 遍历到叶子节点时，计算路径和(注意这里可以有多种形式)

• 对比路径和与目标和相等时，找到一条满足条件的路径

• 看图
  

Java参考代码：

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    //创建一个list存放临时答案
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    //list存放路径
    ArrayList<Integer> path = new ArrayList<Integer>();

    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // dsf调用
        dfs(root,sum);
        return res;

    }
    //dfs函数
    public void dfs(TreeNode root,int sum){
        //特判
        if(root==null){
            return;
        }
        path.add(root.val);
        //求和的减法新式，当sum为0 ，表示找到满足条件的路径
        sum-=root.val;
        if(root.left==null && root.right==null && sum==0){
            res.add(new ArrayList<Integer>(path));
        }
        //对左子树进行DFS
        dfs(root.left,sum);
        //对右子树进行DFS
        dfs(root.right,sum);
        path.remove(path.size()-1);
    }
}

复杂度分析：

时间复杂度：O(N^2) 其中N为节点数。

其中 N 是树的节点数。在