dfs递归解法

1. 全局变量 ArrayList<ArrayList<>> ll保存所有路径
2. 递归调用方法
3. 传参：

• 上一级传递过来的root根节点
• 上一级传递过来的路径
• 上一级传递过来的数值

错误解法

错误解法：比较数值，小于期望值的就中断
错误原因：未考虑负数情况

public class Solution {
    ArrayList<ArrayList<Integer>> ll = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        ArrayList<Integer> path = new ArrayList();
        rec(root,path,expectNumber);
        return ll;
    }
    public void rec(TreeNode root, ArrayList<Integer> path, int expectNumber){
        if(root == null){
            return;
        }
        ArrayList<Integer> newPath = new ArrayList(path);
        if(expectNumber < root.val){
            return;
        }else if(expectNumber == root.val){
            newPath.add(expectNumber);
            if(root.left == null && root.right == null){
                ll.add(newPath);
            }
        }else{
            newPath.add(root.val);
            int n = expectNumber - root.val;
            rec(root.left,newPath,n);
            rec(root.right,newPath,n);
        }
    }
    
}

正确解法

1、先判断是否叶子节点
2、判断是否等于预期值

import java.util.*;
public class Solution {
     ArrayList<ArrayList<Integer>> ll = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        ArrayList<Integer> path = new ArrayList();
        rec(root,path,expectNumber);
        return ll;
    }
    public void rec(TreeNode root, ArrayList<Integer> path, int expectNumber){
        if(root == null){
            return;
        }
        ArrayList<Integer> newPath = new ArrayList(path);
        newPath.add(root.val);
        if(root.left != null){
            rec(root.left, newPath, expectNumber - root.val);
        }
        if(root.right != null){
            rec(root.right, newPath, expectNumber - root.val);
        }
        if(root.left == null && root.right == null){
            if(root.val == expectNumber){
                ll.add(newPath);
            }
        }
    }
    
}