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

方法一（深度优先搜索）

1.题意整理

• 给定一颗二叉树以及一个整数sum，二叉树中每个节点对应一个节点值。
• 找出二叉树中所有的从根节点到叶子节点的节点值之和等于sum的路径。

2.思路整理

可以利用深度优先搜索，遍历所有可能的路径，然后看某个路径的和是否等于sum，如果存在这样的路径，则加入到结果集。

• 递归终止条件：当搜索完所有路径，即root为空，还没有找到合法路径，直接返回false。
• 递归如何传递：每次需要往左右子树方向递归，sum的值要减去当前节点值，如果遇到叶子节点，并且sum为0，说明路径合法，将当前路径直接加入到结果集。

图解展示：

3.代码实现

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<>>
     */
    //记录最终结果
    ArrayList<ArrayList<Integer>> res=new ArrayList<>();
    //记录某一条路径
    ArrayList<Integer> path=new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        //为空直接返回结果
        if(root==null) return res;
        //递归
        dfs(root,sum);
        return res;
    }
    
    private void dfs(TreeNode root,int sum){
        //递归终止条件
        if(root==null) return;
        //期望的路径和expectNumber减去当前节点值
        sum-=root.val;
        //加入到路径
        path.add(root.val);
        //如果为叶子节点，并且expectNumber为0，说明是合法路径，直接加入到res
        if(root.left==null&&root.right==null&&sum==0){
            res.add(new ArrayList<>(path));
        }
        //往左右子树递归
        dfs(root.left,sum);
        dfs(root.right,sum);
        //回溯到上一个节点
        path.remove(path.size()-1);
    }
}

4.复杂度分析

• 时间复杂度：需要遍历二叉树中所有节点，并且每个节点的访问次数不超过2，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：递归栈的深度为$lo{g}_{2}nlog\_2n$，当退化为链表时，深度为n，同时需要额外大小为n的临时list存储路径，所以空间复杂度为$O(n)O(n)$。