題目：輸入一顆二叉樹的根節(jié)點(diǎn)和一個(gè)整數(shù)焊唬，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑寸认。
練習(xí)地址
https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca
https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
參考答案
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
find(root, target, 0, new ArrayList<Integer>(), result);
return result;
}
private void find(TreeNode node, int target, int sum, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result) {
sum += node.val;
path.add(node.val);
// 如果是葉節(jié)點(diǎn)纵顾，并且路徑上節(jié)點(diǎn)值的和等于輸入的值，則打印出這條路徑
if (node.left == null && node.right == null) {
if (sum == target) {
ArrayList<Integer> list = new ArrayList<>();
for (Integer val : path) {
list.add(val);
}
result.add(list);
}
} else {
// 如果不是葉節(jié)點(diǎn)间唉，則遍歷它的子節(jié)點(diǎn)
if (node.left != null) {
find(node.left, target, sum, path, result);
}
if (node.right != null) {
find(node.right, target, sum, path, result);
}
}
// 在返回父節(jié)點(diǎn)之前绞灼，在路徑上刪除當(dāng)前節(jié)點(diǎn)
path.remove(path.size() - 1);
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n^2)。
- 空間復(fù)雜度：O(n)呈野。
