二叉树dfs遍历。。。

题目是要找一条从根节点出发，到叶子节点的路径，且这个路径上节点的和要等于某个值。
典型的dfs遍历二叉树，遍历的时候用一个链表记录前面的路径，每次递归的时候传入还剩多少数值没有加。全局有一个ArrayList<ArrayList<Integer>> finalResult 用来存结果。

每一轮递归，都要先判断还剩下没加的数是否小于当前节点的数值，如果小于，就直接返回，说明当前节点往后的加起来都会比指定数值要大。
然后将当前节点的数值加到路径的末尾，
如果剩下没加的数字比当前节点的数字大，那么进入下一轮的递归。递归之前先判断左右孩子是否为空。下一轮递归要把剩下没加的数字减去当前节点的数值。
如果剩下没加的数字和当前节点的数字一样大，那么就把当前结果保存到finalResult中。
最后将当前节点的数值从路径末尾去掉。

import java.util.LinkedList;
import java.util.Arrays;

public class Solution {
    public ArrayList<ArrayList<Integer>> finalResult = new ArrayList<>();

    public void dfs(TreeNode root, LinkedList<Integer> list, int lsum){

        int nodeNum = root.val;
        if(lsum<nodeNum){
            return;
        }
        list.add(nodeNum);
        if(lsum>nodeNum){
            if(root.left!=null){
                dfs(root.left, list, lsum-nodeNum);
            }
            if(root.right!=null){
                dfs(root.right, list, lsum-nodeNum);
            }
        }else if(lsum==nodeNum&&root.left==null&&root.right==null){
            ArrayList<Integer> result = new ArrayList<>(list);
            finalResult.add(result);
        }
        list.removeLast();

    }

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root==null){
            return finalResult;
        }
        LinkedList<Integer> list = new LinkedList<>();
        dfs(root, list, target);
        return finalResult;
    }
}