给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

给定如下二叉树，以及目标和 sum = 22，

5             / \            4   8           /   / \          11  13  4         /  \    / \        7    2  5   1

返回:

[   [5,4,11,2],   [5,8,4,5]]

 

/**分别往左子树，右子树递归遍历所有路径，每次递归就减去相应的节点值，到了叶子结点,如果剩余值与叶子结点值相等，则该条路径符合要求，记录下该条路径，不符合的中间结果就pop掉 */class Solution {    List
     
      
       > res = new ArrayList<>();    public List
       
        
         > pathSum(TreeNode root, int sum) {        if(root == null) return res;        List
         
           path = new ArrayList<>();        dfs(root,sum,path);        return res;    }    private void dfs(TreeNode root, int sum, List
          
            path){ path.add(root.val); if(root.left == null && root.right == null && root.val == sum) //如果剩余值与叶子结点值相等 res.add(new ArrayList
           
            (path)); if(root.left != null) dfs(root.left,sum-root.val,path); if(root.right != null) dfs(root.right,sum-root.val,path); path.remove(path.size()-1); }}