113. Path Sum II

题目描述（中等难度）

112 题 的升级版，给定一个sum，输出从根节点开始到叶子节点，和为sum 的所有路径可能。

直接在 112 题 的基础上改了，解法没有新内容，大家可以过去看一看。

解法一 递归

112 题 的解法是下边的样子。

public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } return hasPathSumHelper(root, sum); } private boolean hasPathSumHelper(TreeNode root, int sum) { //到达叶子节点 if (root.left == null && root.right == null) { return root.val == sum; } //左孩子为 null if (root.left == null) { return hasPathSumHelper(root.right, sum - root.val); } //右孩子为 null if (root.right == null) { return hasPathSumHelper(root.left, sum - root.val); } return hasPathSumHelper(root.left, sum - root.val) || hasPathSumHelper(root.right, sum - root.val); }

这里的话我们需要一个ans变量来保存所有结果。一个temp变量来保存遍历的路径。需要注意的地方就是，java中的list传递的是引用，所以递归结束后，要把之前加入的元素删除，不要影响到其他分支的temp。

import java.util.ArrayList; import java.util.List; class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int x){val=x;} } public class Path_Sum_II { public static List<List<Integer>> pathSum(TreeNode root,int sum){ List<List<Integer>> ans=new ArrayList<>(); List<Integer> temp=new ArrayList<>(); if(root==null) return ans; hasPathSumHelper(root,sum,temp,ans); return ans; } private static void hasPathSumHelper(TreeNode root,int sum,List<Integer> temp,List<List<Integer>>ans) { if(root.left==null && root.right==null) { if(root.val==sum) { temp.add(root.val); ans.add(new ArrayList<>(temp)); temp.remove(temp.size()-1); } return ;//返回上一级 } if(root.left==null) { temp.add(root.val); hasPathSumHelper(root.right,sum-root.val,temp,ans); temp.remove(temp.size()-1); return ; } if(root.right==null) { temp.add(root.val); hasPathSumHelper(root.left,sum-root.val,temp,ans); temp.remove(temp.size()-1); return ; } temp.add(root.val); hasPathSumHelper(root.left,sum-root.val,temp,ans); temp.remove(temp.size()-1); temp.add(root.val); hasPathSumHelper(root.right,sum-root.val,temp,ans); temp.remove(temp.size()-1); } public static void main(String args[]) { TreeNode[] node=new TreeNode[10]; node[0]=new TreeNode(5); node[1]=new TreeNode(4); node[2]=new TreeNode(8); node[3]=new TreeNode(11); node[4]=new TreeNode(13); node[5]=new TreeNode(4); node[6]=new TreeNode(7); node[7]=new TreeNode(2); node[8]=new TreeNode(5); node[9]=new TreeNode(1); node[0].left=node[1]; node[0].right=node[2]; node[1].left=node[3]; node[2].left=node[4]; node[2].right=node[5]; node[3].left=node[6]; node[3].right=node[7]; node[5].left=node[8]; node[5].right=node[9]; int sum=22; List<List<Integer>> ans=pathSum(node[0],sum); System.out.println(ans); } }

参考文献

1.https://zhuanlan.zhihu.com/p/75266560