从零学算法113-Toy模板网

这篇具有很好参考价值的文章主要介绍了从零学算法113。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

113.给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
叶子节点是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]文章来源地址https://www.toymoban.com/news/detail-676810.html

我的思路：不用想，看到树，看到路径，不 dfs 等什么。接下来就是入参，root 肯定是要的，不然我都不知道我遍历到哪个节点了，然后要计算路径伤的和，肯定也需要一个 int 变量。接下来就是递归的出口，首先如果遍历到节点都为 null 了，那肯定是要返回了，其次根据题意如果遍历到叶子结点，路径和是我们要的，那就把这一条路径添加到结果 list 中。递归内容就是不断更新 root 以及计算的路径和了

  List<List<Integer>> ans = new ArrayList<>();
  List<Integer> list = new ArrayList<>();
  public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
      dfs(root,targetSum);
      return ans;
  }
  void dfs(TreeNode root, int sum){
      if(root==null)return;
      list.add(root.val);
      // 注意递归到此时如果路径可行的话， sum 其实还剩下 root.val 没减
      if(root.left==null && root.right==null && sum==root.val)
      	// 防止 ans 中的路径随递归继续改变
          ans.add(new ArrayList(list));
      dfs(root.left,sum-root.val);
      dfs(root.right,sum-root.val);
      // 路径恢复
      list.remove(list.size()-1);
  }

其实按我之前想的，递归的出口只要设置为 root 为 null 就够了，只不过在 return 之前判断一下 sum 是否为 0 决定是否为一个可行路径。但是当你到达可行路径的叶子结点后，你会继续往左右分叉，此时两个为 null 的节点都符合要求，也是说最后答案是对的，不过会多一份重复的答案。所以在 root 为 null 的前一步也就是 root.left==null && root.right==null 时就应该判断路径是否可行。

  // 我之前想的错误代码
  List<Integer> list = new ArrayList<>();
  List<List<Integer>> ans = new ArrayList<>();
  public List<List<Integer>> pathSum(TreeNode root, int target) {
      dfs(root,target);
      return ans;
  }
  public void dfs(TreeNode root,int sum){
      if(root==null){
          if(sum==0)ans.add(new ArrayList(list));
          return;
      } 
      list.add(root.val);
      dfs(root.left,sum-root.val);
      dfs(root.right,sum-root.val);
      // 路径恢复
      list.remove(list.size()-1);
  }