LeetCode 二叉树路径问题 Path SUM（①②③）总结
描述
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]
解析
除了要判断是否有这样的一个path sum，还需要把所有的都可能性结果都返回，所以就用传统的DFS递归解决子问题。
将当前节点root的值放入list中更新sum值，判断当前节点是否满足递归条件root.left == null && root.right == null&&sum == 0；
若满足，则将存有当前路径的list值存入最后的大list中
然后依次递归左子树和右子树
从存有当前路径的list中去除最后一个节点，这样便可以返回到了当前叶子节点的父节点
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<List<Integer>> listAll = new ArrayList<>();
List<Integer> list = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null)
return listAll;
list.add(root.val);
sum -= root.val;
if(root.left == null && root.right == null && sum == 0)
listAll.add(new ArrayList<Integer>(list));
pathSum(root.left, sum);
pathSum(root.right, sum);
list.remove(list.size() - 1);
return listAll;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void pathSumHelper(TreeNode root, int sum, List<Integer> sumlist, List<List<Integer>> pathlist) {
if (root == null)
return;
sumlist.add(root.val);
sum = sum - root.val;
if (root.left == null && root.right == null) {
if (sum == 0) {
pathlist.add(new ArrayList<Integer>(sumlist));
}
} else {
if (root.left != null)
pathSumHelper(root.left, sum, sumlist, pathlist);
if (root.right != null)
pathSumHelper(root.right, sum, sumlist, pathlist);
}
sumlist.remove(sumlist.size() - 1);
} public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> pathlist = new ArrayList<List<Integer>>();
List<Integer> sumlist = new ArrayList<Integer>();
pathSumHelper(root, sum, sumlist, pathlist);
return pathlist;
}
}