题解 | #二叉树中和为某一值的路径(二)#

方法一（深度优先搜索）

1.题意整理

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

2.思路整理

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

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

图解展示：

3.代码实现

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

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

4.复杂度分析

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