leetcode113.路径总和II

leetcode113.路径总和II

二月 23, 2020

leetcode113. 路径总和 II

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

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

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

返回:
[
[5,4,11,2],
[5,8,4,5]
]

和路径总和那道题一样，只是需要记录路径，并且把所有可能的路径都找出来，我是用递归的方法写的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ArrayList<Integer>list=new ArrayList<>();
    public List<List<Integer>>res=new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
         dfs(root,0,sum);
        return res;
    }
    public void dfs(TreeNode root,int sum,int target){
        if(root==null)return;
        sum+=root.val;
        list.add(root.val);
        if(root.left==null&&root.right==null){
            if(sum==target){
                //ArrayList<Integer>newList=new ArrayList<>();
                //newList.addAll(new ArrayList<>(list));
                res.add(new ArrayList<>(list));
            }
        }
        dfs(root.left,sum,target);
        dfs(root.right,sum,target);
        //下面要回溯了，说明这个时候的节点不满足要求，必须从list里面删除
        list.remove(list.size()-1);
    }

leetcode 31/100