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

using System.Collections.Generic;
/*
public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode (int x)
    {
        val = x;
    }
}*/

class Solution
{
    public List<List<int>> FindPath(TreeNode root, int expectNumber)
    {
        // write code here
        List<List<int>> routes=new List<List<int>>();
        List<int> route=new List<int>();
        if(root==null)
            return routes;
        Route(root,expectNumber,route,ref routes);
        return routes;
        
    }
    
    public void Route(TreeNode root,int sum, List<int> route, ref List<List<int>> routes)
    {
        route.Add(root.val);
        if(root.val==sum && root.left==null && root.right==null)
        {
            routes.Add(new List<int>(route));   //由于需要回溯，List是引用类型，所以添加数组时需要保存复制版本，否则最后添加的list会为空
            //return;
        }
        if(root.left!=null)
        {
             Route(root.left, sum-root.val ,route, ref  routes);   
        }
        if(root.right!=null)
        {
            Route(root.right, sum-root.val , route, ref  routes);
        }
        route.RemoveAt(route.Count-1);
            
    }
    
}