牛客题解-NC8二叉树路径之和

发表于 更新于 分类于 阅读次数：

题目

给定一个二叉树和一个值 sum sum，请找出所有的根节点到叶子节点的节点值之和等于 sum sum 的路径， 例如： 给出如下的二叉树， sum=22 sum=22，

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

示例1

输入：

1
{1,2},1

输出：

1
[]

示例2

输入：

1
{1,2},3

输出：

1
[[1,2]]

思路

分析

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> tmp = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // write code here
        dfs(root, sum, 0);
        return res;
    }
    
    public void dfs(TreeNode root, int sum, int cur){
        if(root == null) return;
        tmp.add(root.val);
        cur += root.val;
        if(root.left == null && root.right == null){
            if(cur == sum){
                res.add(new ArrayList<>(tmp));
            }
        }else{
                dfs(root.left, sum, cur);
                dfs(root.right, sum, cur);
            }
            tmp.remove(tmp.size() - 1);
    }
}