leetcode_113

题目来源：https://leetcode.com/problems/path-sum-ii/

代码：

/**

• Definition for a binary tree node.
• public class TreeNode {
• int val;
• TreeNode left;
• TreeNode right;
• TreeNode(int x) { val = x; }

• }
  */
  class Solution {
  public List<List> pathSum(TreeNode root, int sum) {

  List<List<Integer>> list = new LinkedList<>();
  if(root == null){
      return list;
  }
  List<Integer> currentList = new ArrayList<>();
  currentList.add(root.val);
  traverse(list,currentList,root,sum);
  return list;
  

  }
  public void traverse(List<List> list,List currentList,TreeNode root,int sum){

  if(root.left == null && root.right == null){
      if (root.val == sum){
          list.add(new ArrayList<>(currentList));
      }
      return;
  }
  if(root.left != null){
      currentList.add(root.left.val);
      traverse(list,currentList,root.left,sum-root.val);
      currentList.remove(currentList.size()-1);
  }
  if(root.right != null){
      currentList.add(root.right.val);
      traverse(list,currentList,root.right,sum-root.val);
      currentList.remove(currentList.size()-1);
  }
  

  }
  }