/*
 * 几个要点：
 * 1. 将nodeList和pathList定义成全局变量，避免在方法中的多次传递
 * 2. 在pathList中添加nodeList时，因为nodeList会不断变化，所以必须新建一个list存入
 *    复制ArrayList的方法：newList=new ArrayList<Integer>(oldList)(复制内容，而不是复制地址，注意与newList=oldList的区分）
 * 3. 在当前结点完成左右子树的路径搜索后，记得删除nodeList中的当前结点
 * 4. target是基本数据类型int，不会受到方法的影响而改变
 */
private ArrayList<Integer> nodeList= new ArrayList<>();
private ArrayList<ArrayList<Integer>> pathList = new ArrayList<>();

public ArrayList<ArrayList<Integer>> FindPath(TreeNode node,int target) {
    if(node==null)
        return pathList;
    nodeList.add(node.val);
    target-=node.val;
    if(target==0 && node.left==null && node.right==null) {  //叶子结点
        //长度大的nodeList插入到pathList的前面
        int i=0;
        while(i<pathList.size() && nodeList.size()<pathList.get(i).size() ) //记得防止越界
                i++;
        pathList.add(i, new ArrayList<Integer>(nodeList));  //nodeList会随方法变化，必须新建一个list存入pathList中！
    }else {  //不是叶子结点
        pathList=FindPath(node.left, target);
        pathList=FindPath(node.right, target);
    }
    nodeList.remove(nodeList.size()-1);  //记得删除当前结点
    return pathList;
}

class Solution {
    vector<vector<int> >allRes;
    vector<int> tmp;
    void dfsFind(TreeNode * node , int left){
        tmp.push_back(node->val);
        if(left-node->val == 0 && !node->left && !node->right)
            allRes.push_back(tmp);
        else {
            if(node->left) dfsFind(node->left, left-node->val);
            if(node->right) dfsFind(node->right, left-node->val);
        }
        tmp.pop_back(); 
    }
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        if(root) dfsFind(root, expectNumber);
        return allRes;
    }
};

/*
非递归法：后序遍历
1.进栈时候，把值同时压入路径的向量数组，修正路径的和
2.出栈时候，先判断和是否相等，且该节点是否是叶节点，
判断完成后保持和栈一致，抛出路径，修改路径的和
3.向量数组和栈的操作要保持一致
*/
class Solution {
public:
	vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
		stack<TreeNode*> s;
		vector<int> v;
		vector<vector<int> > res;
		while (root || !s.empty()){
			while (root){
				s.push(root); v.push_back(root->val); expectNumber -= root->val;
				//能左就左，否则向右
				root = root->left ? root->left : root->right;
			}
			root = s.top();
			if (expectNumber == 0 && root->left == NULL && root->right == NULL)
				res.push_back(v);
			s.pop(); v.pop_back(); expectNumber += root->val;
			//右子数没遍历就遍历，如果遍历就强迫出栈
			if (!s.empty() && s.top()->left == root)
				root = s.top()->right;
			else
				root = NULL;//强迫出栈
		}
		return res;
	}
};

public class Solution {
    private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
    private ArrayList<Integer> list = new ArrayList<Integer>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null) return listAll;
        list.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null) 
            listAll.add(new ArrayList<Integer>(list));
        FindPath(root.left, target);
        FindPath(root.right, target);
        list.remove(list.size()-1);
        return listAll;
    }
}

//非递归版本
//思路：
1.按先序遍历把当前节点cur的左孩子依次入栈同时保存当前节点，每次更新当前路径的和sum；
2.判断当前节点是否是叶子节点以及sum是否等于expectNumber，如果是，把当前路径放入结果中。
3.遇到叶子节点cur更新为NULL，此时看栈顶元素，如果栈顶元素的把栈顶元素保存在last变量中，同时弹出栈顶元素，当期路径中栈顶元素弹出，sum减掉栈顶元素，这一步骤不更改cur的值；
4.如果步骤3中的栈顶元素的右孩子存在且右孩子之前没有遍历过，当前节点cur更新为栈顶的右孩子，此时改变cur=NULL的情况。

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL){}
}

vector<vector<int> > FindPath(TreeNode *root, int expectNumber){
    vector<vector<int> > res;    
    if (root == NULL)
        return res;
    stack<TreeNode *> s;
    s.push(root);
    int sum = 0; //当前和
    vector<int> curPath; //当前路径
    TreeNode *cur = root; //当前节点
    TreeNode *last = NULL; //保存上一个节点
    while (!s.empty()){
        if (cur == NULL){
            TreeNode *temp = s.top();
            if (temp->right != NULL && temp->right != last){
                cur = temp->right; //转向未遍历过的右子树
            }else{
                last = temp; //保存上一个已遍历的节点
                s.pop();
                curPath.pop_back(); //从当前路径删除
                sum -= temp->val;
            }  }
        else{
            s.push(cur);
            sum += cur->val;
            curPath.push_back(cur->val);
            if (cur->left == NULL && cur->right == NULL && sum == expectNum){
                res.push_back(curPath);
            }
            cur = cur->left; //先序遍历，左子树先于右子树
        }
    }
    return res;
}

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,
            int target) {
        ArrayList<ArrayList<Integer>> pathList=
                new ArrayList<ArrayList<Integer>>();
        if(root==null)
            return pathList;
        Stack<Integer> stack=new Stack<Integer>();
        FindPath(root,target,stack,pathList );
        return pathList;
        
    }
    private void FindPath(TreeNode root, int target,
            Stack<Integer> path,
            ArrayList<ArrayList<Integer>> pathList) {
        if(root==null)
            return;
        if(root.left==null&&root.right==null){
            if(root.val==target){
                ArrayList<Integer> list=
                        new ArrayList<Integer>();
                for(int i:path){
                    list.add(new Integer(i));
                }
                list.add(new Integer(root.val));
                pathList.add(list);
            }
        }
        else{
            path.push(new Integer(root.val));
            FindPath(root.left, target-root.val, path, pathList);
            FindPath(root.right, target-root.val, path,  pathList);
            path.pop();
        }
        
    }
}

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if (root == null) {
            return res;
        }
        findPath(root, target);
        return res;
    }
    
    public void findPath(TreeNode root, int target) {
        //因为FindPath中和 下面程序中都进行了判null操作，root绝对不可能为 null
        path.add(root.val);
        //已经到达叶子节点，并且正好加出了target
        if (root.val == target && root.left == null && root.right == null) {
            //将该路径加入res结果集中
            res.add(new ArrayList(path));
        }
        //如果左子树非空，递归左子树
        if (root.left != null) {
            findPath(root.left, target - root.val);
        }
        //如果右子树非空，递归右子树
        if (root.right != null) {
            findPath(root.right, target - root.val);
        }
        //无论当前路径是否加出了target，必须去掉最后一个，然后返回父节点，去查找另一条路径，最终的path肯定为null
        path.remove(path.size() - 1);
        return;
    }
    
}

import java.util.ArrayList;
public class Solution {
   private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
	private ArrayList<Integer> list = new ArrayList<>();
	public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
		if(root == null) return res;
		list.add(root.val);
		target -= root.val;
		if(target == 0 && root.left == null && root.right == null) {
			res.add(new ArrayList<Integer>(list));
		}
		FindPath(root.left, target);
		FindPath(root.right, target);
		list.remove(list.size() - 1);
		return res;
	}
}

python 解法：

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        res=[]
        treepath=self.dfs(root)
        for i in treepath:
            if sum(map(int,i.split('->')))==expectNumber:
                res.append(list(map(int,i.split('->'))))
        return res

    def dfs(self, root):
        if not root: return []
        if not root.left and not root.right:
            return [str(root.val)]
        treePath = [str(root.val) + "->" + path for path in self.dfs(root.left)]
        treePath += [str(root.val) + "->" + path for path in self.dfs(root.right)]
        return treePath

9行：

class Solution:
    def FindPath(self, root, expectNumber):
        return [map(int, i.split("->")) for i in self.dfs(root) if sum(map(int, i.split('->'))) == expectNumber]
    def dfs(self, root):
        if not root: return []
        if not root.left and not root.right: return [str(root.val)]
        treePath = [str(root.val) + "->" + path for path in self.dfs(root.left)]
        treePath += [str(root.val) + "->" + path for path in self.dfs(root.right)]
        return treePath

class Solution {
    void TreePath(TreeNode* root,int target,vector<int> &path,vector<vector<int> > &pathList)
    {
        if(root == NULL)
            return ;
        path.push_back(root->val);
        bool isLeaf = root->left==NULL && root->right==NULL;
        if(root->val==target && isLeaf)
        {
            pathList.push_back(path);
            path.pop_back();
        }
        else
        {
            TreePath(root->left,target - root->val,path,pathList);
            TreePath(root->right,target - root->val,path,pathList);
            path.pop_back();
        }
    }
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber)
    {
        vector<vector<int> > FindPath;
        vector<int> Path;  // 为了保存每一次递归的值,这里声明了一个path
        if(root == NULL)
            return FindPath;
        TreePath(root,expectNumber,Path,FindPath);
        return FindPath;
    }
};

注意两点：1）每次遍历到一个node时，expectNumber -= node->val,这样，遍历到叶子时，只要判断expectNumber是否为0即可。
          2）用vector<int>& tmp记录路径而不是用vector<int> tmp，后者占用大量空间时间。
                       使用前者只需要在每次递归调用返回时，pop_back()一下，就可以了。 public:   
    void HelperFunc(vector<vector<int> >& ret, vector<int>& tmp, TreeNode* node, int expectNumber){
        tmp.push_back(node->val);
        expectNumber -= node->val;
        if(node->left==NULL && node->right==NULL){
            if(expectNumber == 0)
                ret.push_back(tmp);
        }
        if(node->left!=NULL){
            HelperFunc(ret, tmp, node->left, expectNumber);
            tmp.pop_back();
        }
        if(node->right!=NULL){
            HelperFunc(ret, tmp, node->right, expectNumber);
            tmp.pop_back();
        }
    }   
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > ret;
        vector<int> tmp;
        if(root!=NULL)
            HelperFunc(ret, tmp, root, expectNumber);
        return ret;
    }
};

class Solution {
public:
    vector<vector<int> > ans;
    vector<int> v;

    void solve(TreeNode* node, int res){
        v.push_back(node->val);
        if(res - node->val == 0 && !node->left && !node->right)
            ans.push_back(v);
        else{
            if(node->left) solve(node->left, res - node->val);
            if(node->right) solve(node->right, res - node->val);
        }
        v.pop_back();
    }

    vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
        if(root) solve(root, expectNumber);
        return ans;
    }
};

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):

        self.list = []
        self.list1 = []
    def FindPath(self, root, expectNumber):
        if root == None:
            return self.list1
        # print('********')
        self.list.append(root.val)
        # print(list)
        expectNumber -= root.val
        # print('----', target)
        if expectNumber == 0 and root.left == None and root.right == None:
            newlist = []
            for line in self.list:
                newlist.append(line)
            self.list1.append(newlist)
        # print('*****', list1)
        # list1.append(proot.val)
        # print(list1)
        # print(list)
        # print('********')
        # print(proot.val)
        # print('********')

        self.FindPath(root.left, expectNumber)

        self.FindPath(root.right, expectNumber)
        self.list.pop()
        return self.list1

非递归实现 ，出栈是后序遍历
 private  ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
    
    public  ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        HashMap<TreeNode, Boolean> rightDealed = new HashMap<>();
        TreeNode node = root;
        while (node != null || stack.size() > 0) {
            if (node != null) { 
                stack.push(node);
                System.out.println("push:" + node.val);//先序
                addPath(node,stack,target);
                node = node.left;
            } else {
                node = stack.peek();
                if (rightDealed.get(node) != null) {//已访问过右节点 该出栈了
                    stack.pop();
                    System.out.println("pop:" + node.val);//后序
                    node=null;
                }else{                              //若未访问右节点先不出栈
                    rightDealed.put(node, true);
                    node = node.right;

                }
            }
        }
        return listAll;
    }
    
    public void addPath(TreeNode node,Stack<TreeNode> stack,int target){
        if(node.left==null&&node.right==null){
            ArrayList<Integer> list=new ArrayList();
            int total=0;
            for (TreeNode treeNode : stack) {
                list.add(treeNode.val);
                total=total+treeNode.val;
                System.out.print(treeNode.val + " ");
            }
            if(total==target){
                listAll.add(list);
            }
        }
    }

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<Integer> list1=new ArrayList<>();
        getPath(root, target, list1);
        return list;
    }
    
    public void getPath(TreeNode root, int target, ArrayList<Integer> list1){                 
        if(root==null|| target<0) return;
        list1.add(root.val);
        if(target-root.val==0 && root.left==null && root.right==null){
            list.add(new ArrayList<Integer> (list1));
        }
        getPath(root.left, target-root.val, list1);
        getPath(root.right, target-root.val, list1);
        list1.remove(list1.size()-1);
    }
}

    # 后序遍历，只有在叶子结点计算完毕符合要求的路径才会返回路径的节点列表，否则返回空列表
    def FindPath(self, root, expectNumber):
        # write code here
        if not root: # 输入为空树时，返回空列表
            return []
        if not root.left and not root.right: # 到达叶子结点
            return [[root.val,],] if root.val == expectNumber else [] # 如果叶子结点的值符合最后需要的那一个值，需要返回该路径，否则返回空列表
        if root.val < expectNumber: # 非叶子节点时，如果当前节点值小于需要值，则继续遍历
            x = self.FindPath(root.left,expectNumber-root.val) + self.FindPath(root.right,expectNumber-root.val) # 遍历结果为左右子树遍历结果的集合
            return sorted([[root.val,]+each for each in x],key=lambda x:len(x),reverse=True)if x else [] # 如果有结果则加上本节点并且对结果长度依次排序，否则返回空列表
        else: # 非叶子节点时，如果当前节点值已经超过需要的数，则提前结束该分支的遍历
            return []

public class Solution {
    private ArrayList<ArrayList<Integer>> res;
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        res = new ArrayList<>();
        backtrack(root, target, new ArrayList<Integer>());
        return res;
    }
    private void backtrack(TreeNode root, int target, ArrayList<Integer> ls) {
        //终止条件
        if(root == null) return;
        //修正target
        target -= root.val;
        //添加进list
        ls.add(root.val);
        //判断是否满足要求
        if(target == 0 && root.left == null && root.right == null) {
            //将当前的ls加入到结果
            res.add(new ArrayList<Integer>(ls));
        }
        //递归
        backtrack(root.left, target, ls);
        backtrack(root.right, target, ls);
        //删除不满足要求的
        ls.remove(ls.size() - 1);
    }
}

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 {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
        if (root == null) {
            return paths;
        }
        ArrayList<Integer> path = new ArrayList<Integer>();
        findPaths(root, target, path, paths);
        return paths;
    }
    
    public void findPaths(TreeNode root, int target, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths){
        path.add(root.val);
        if (target == root.val && root.left == null && root.right == null) {
            paths.add(path);
            return;
        }
        ArrayList<Integer> path2 = new ArrayList<Integer>();
        path2.addAll(path);
        if (root.left != null) {
            findPaths(root.left, target - root.val, path, paths);
        }
        if (root.right != null) {
            findPaths(root.right, target - root.val, path2, paths);
        }
    }
   
}

递归四部曲

1. 递归终止条件
2. 当前层要做的事情
3. 下沉到下一层
4. 恢复当前层的状态（if needed）

import java.util.ArrayList;
public class Solution {
    private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null || target == 0) return ret;
        backtracing(root,target,new ArrayList<>());
        return ret;
    }
    public void backtracing(TreeNode root , int target, ArrayList<Integer> path){
        //1.递归终止条件
        //到达叶子的左右子树（空）时返回
        if(root == null)
            return;
        //2.当前层要做的事情
        path.add(root.val);
        target -= root.val;
        //如果当前层是叶子节点且路径找对了，添加到ret里
        if(target == 0 && root.left == null && root.right == null)
            ret.add(new ArrayList<>(path));
        //3.不满足条件就下沉drill down
        else{
            backtracing(root.left,target,path);
            backtracing(root.right,target,path);
        }
        //4.恢复当前层被递归破坏的状态
        path.remove(path.size()-1);
    }
}

/* 思路更为清晰的递归方式 -- path与ret均定义在函数内部 */
/* 递归方式 */
class Solution {
    void DFSFindPath(TreeNode* root, int rest, vector<vector<int>> &path, vector<int> &ret)
    {
        rest -= root->val;  // 减去当前结点的值
        ret.push_back(root->val);
        
        // 如果是叶子结点，则看此时路径和是否等于exceptNumber，是则保留该路径
        if(root->left == nullptr && root->right == nullptr)
            if(rest == 0) path.push_back(ret);
        
        // 如果不是叶子结点，若rest != 0,则递归进入左右子树（注：若rest==0，则删除该结点后返回）
        if( rest != 0 && root->left != nullptr)
            DFSFindPath(root->left,rest,path,ret);
        if( rest != 0 && root->right != nullptr)
            DFSFindPath(root->right,rest,path,ret);
        
        ret.pop_back();   // 退出该结点前，在路径中删除该结点     
    }
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) 
    {
        vector<vector<int>> path;
        vector<int> ret;
        if(root != nullptr)
            DFSFindPath(root,expectNumber,path,ret);
        
        return path;
    }
};