leetcode 113. 路径总和 II

题目描述

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
相关话题：树、深度优先搜索    难度：中等
说明: 叶子节点是指没有子节点的节点。

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

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

思路：这道题和112题很像，唯一不同是它需要把路径保存下来。
那么我们就需要想办法把遍历过的路径保存下来。

• 如果当前节点是null，直接return，否则加到list。
• 如果当前节点是叶子节点，并且sum已经累加到了目标和，说明这条路径是满足条件的，将list加入到路径容器res中。
  注意：不能res.add(list)，res保存的是list的引用，下次list内容修改了，res所保存的值也会修改了，因此我们要保存一个新的list对象，res.add(new ArrayList(list))

• 不满足第二点的话，就递归遍历左子树和右子树，左右子树遍历完，返回前一个节点需要将list的最后一个值删掉。

  
  
  

  如上图遍历到节点7，节点7的左右子树都是空，程序会返回节点11再遍历节点2，那么需要将list中的最后一个元素删掉。(返回上一级的时候删除)

• 代码

public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        pathSum(root,sum,res,list);
        return res;
    }
    public void pathSum(TreeNode root, int sum, List<List<Integer>> res, List<Integer> list){
        if(root == null) return;
        list.add(root.val);
        if(root.left == null && root.right == null && sum == root.val){
            res.add(new ArrayList(list));
        }
        pathSum(root.left,sum-root.val, res, list);
        pathSum(root.right,sum-root.val, res, list);
        list.remove(list.size()-1);
    }