leetcode-797 所有可能的路径

题目描述:给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。提示:

  • n == graph.length
  • 2 <= n <= 15
  • 0 <= graph[i][j] < n
  • graph[i][j] != i
  • 保证输入为有向无环图 (GAD)

代码实现

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
private List<List<Integer>> allPaths = new ArrayList<>();

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<Integer> path = new ArrayList<Integer>();
path.add(0);
allPathsSourceTarget(graph, 0, graph.length - 1, path);
return allPaths;
}

public void allPathsSourceTarget(int[][] graph, int k, int n, List<Integer> path) {
List<Integer> currentPath = new ArrayList<>(path);
if (k == n) {
allPaths.add(currentPath);
return;
}
for (int i : graph[k]){
currentPath.add(i);
allPathsSourceTarget(graph, i, n, currentPath);
currentPath.remove(currentPath.size() - 1);
}
}
}