##題目描述 輸入一顆二叉樹的根節點和一個整數，列印出二叉樹中結點值的和為輸入整數的所有路徑，路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑，
思路
回溯法，
時間復雜度O(n)，空間復雜度O(n)，
代碼
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 {
private ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null) return lists;
list.add(root.val);
target -= root.val;
if(target == 0 && root.left == null && root.right == null) {
lists.add(new ArrayList<Integer>(list));
} else {
FindPath(root.left, target);
FindPath(root.right, target);
}
list.remove(list.size()-1);
return lists;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85169.html
標籤：其他
上一篇：《演算法導論》第二章筆記