01.16
112.路径总和
思路
1.利用深搜遍历思想，找到叶子节点并逐层累加判断是否满足条件
或使用递归思想找到左右节点是否存在满足tar-root.val的节点.
总结
递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
- 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
- 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
- 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
代码
public boolean hasPathSum(TreeNode root, int targetSum) {int sum=0;return getSum(root,sum,targetSum);}public boolean getSum(TreeNode root,int sum,int targetSum) {if (root==null) return false;sum=sum+root.val;if (root.left==null && root.right==null) {if (sum==targetSum)return true;}else {if (root.left!=null && getSum(root.left,sum,targetSum)) return true;if (root.right!=null && getSum(root.right,sum,targetSum)) return true;}return false;}
或
public boolean hasPathSum(TreeNode root, int sum) {if(root == null){return false;}if(root.left == null && root.right == null){return root.val == sum;}return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);}113.路径总和ii
思路
回溯，最后需返还List<List<Integer>>，那么需要使用全局变量，需在递归函数中if (targetSum==0 && root.left==null &&root.right==null) 来添加一个List，那么只需在遍历节点时加入当前节点值即可，并在递归返回上一层时抛出这个值，因此需要使用栈来帮助。LinkendList存在add,removeLast方法，能够模仿栈的操作，而List不行。
总结
ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
代码
class Solution {LinkedList<List<Integer>> res=new LinkedList<>();LinkedList<Integer> path=new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {recur(root,targetSum);return res;}public void recur(TreeNode root,int targetSum) {if (root==null) return;path.add(root.val);targetSum-=root.val;if (targetSum==0 && root.left==null &&root.right==null) res.add(path);recur(root.left,targetSum);recur(root.right,targetSum);path.removeLast();}
}