二叉树根节点到叶子节点和为指定值的路径

1.递归dfs，相当于先序遍历
可以用从根结点到叶子结点的值用sum进行相减，判断有无符合的路径。也可以使用往下累加的方法，找到相应路径，时间复杂度：O（n），遍历所有结点，空间复杂度：O（n）。
import java.util.*;

/*

• public class TreeNode {
• int val = 0;
• TreeNode left = null;
• TreeNode right = null;
• }
• /

public class Solution {
/*
*
* @param root TreeNode类
* @param sum int整型
* @return int整型ArrayList<ArrayList<>>
*/
ArrayList<ArrayList<integer>> res=new ArrayList<>();
public ArrayList<ArrayList<integer>> pathSum (TreeNode root, int sum) {
// write code here
if(root==null)//树为空
return res;
dfs(root,sum,new ArrayList<integer>());
return res;
}
public void dfs(TreeNode root, int sum,ArrayList<integer> list){
if(root==null)return;//结点为空
ArrayList<integer> temp=new ArrayList<>(list);//防止被递归污染，重新定义，其实可以用回溯的思想，就不能再定义了，只不过用完，就需要移除一个结点.
temp.add(root.val);
if(root.left==null&&root.right==null){//该结点为叶子结点
if(sum==root.val){//找到对应的路径了
res.add(temp);
}
//temp.remove(temp.size()-1);//用完，需要移除一个结点
return;
}
dfs(root.left,sum-root.val,temp);//递归左子树
dfs(root.right,sum-root.val,temp);//递归右子树
//temp.remove(temp.size()-1);//用完，需要移除一个结点
}
}
2.非递归方法
用栈（后进先出）实现非递归先序遍历，一路向下逐加，得到符合条件的路径，时间复杂度：O（n），遍历所有结点，空间复杂度：O（n）。辅助空间栈。(借鉴了大佬的思路)
import java.util.</integer></integer></integer></integer></integer>;

/*

• public class TreeNode {
• int val = 0;
• TreeNode left = null;
• TreeNode right = null;
• }
• /

public class Solution {
/**
*
* @param root TreeNode类
* @param sum int整型
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<integer>> pathSum (TreeNode root, int sum) {
// write code here
ArrayList<ArrayList<integer>> res=new ArrayList<>();
if(root==null)//树为空
return res;
Stack<treenode> stackNode=new Stack<>();//遍历结点的栈
Stack<ArrayList<integer>> stackList=new Stack<>();//用于存路径的栈
ArrayList<integer> list=new ArrayList<>();//存放结点值
stackNode.add(root);
list.add(root.val);
stackList.add(list);
while(!stackNode.empty()){
TreeNode node=stackNode.pop();
ArrayList<integer> temp=stackList.pop();
if(node.left==null&&node.right==null&&node.val==sum){
//该结点为叶子结点，且符合当前值
res.add(temp);
}
if(node.right!=null){//右结点不为空
temp.add(node.right.val);
stackList.add(new ArrayList<>(temp));//添加路径
node.right.val+=node.val;
stackNode.push(node.right);
temp.remove(temp.size()-1);//用完进行移除
}
if(node.left!=null){//右结点不为空
temp.add(node.left.val);
stackList.add(new ArrayList<>(temp));//添加路径
node.left.val+=node.val;
stackNode.push(node.left);
temp.remove(temp.size()-1);//用完进行移除
}
}
return res;
}
}</integer></integer></integer></treenode></integer></integer>