113. Path Sum II

[Shawngbk]

使用dfs方式解决，每个路径加到list，但注意不能重复添加结点值，要删除最后一个

/**

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

• } */ public class Solution {

  public List<List> pathSum(TreeNode root, int sum) { List<List> res = new ArrayList<List>(); List list = new ArrayList(); if(root != null) { dfs(root, sum, list, res); } return res; } private void dfs(TreeNode root, int sum, List list, List<List> res) {

  if(root != null) {
      list.add(root.val);
      if(root.left == null && root.right == null && root.val == sum) {
          res.add(new ArrayList(list));
      }
      if(root.left != null) {
          dfs(root.left, sum - root.val, list, res);
      }
      if(root.right != null) {
          dfs(root.right, sum - root.val, list, res);
      }
      //要在每次递归之前把list中的最后一个元素删除，因为如果不删除，遍历左子树后继续遍历右子树，左节点的值也会被加入到下一个路径中
      if(list.size() != 0)
      list.remove(list.size() - 1);
  }

  } }

[Shawngbk]

bloomberg