アルゴリズム-ツリー検索とtargetのパス
4904 ワード
1.およびtargetへのパス
ルートノードからリーフノードへ、指定した値へのパスを見つけるツリーがあります. 0
/ \
1 2
/ \
5 4
例えばtarget=6の場合、[0,1,5],[0,2,4]を返す必要がある
2.解法
遡及法で検索し、解があれば直接戻り、解がなければ前のレイヤに戻ります.ArrayList<Integer> list = new ArrayList<>(); //
ArrayList<ArrayList<Integer>> paths = new ArrayList<>(); //
public ArrayList<ArrayList<Integer>> findPath(TreeNode root, int target) {
if (root == null) return paths;
list.add(root);
target -= root.val;
if (target == 0 && root.left == null && root.right == null) {
paths.add(new ArrayList<Integer>(list)); // ，
}
findPath(root.left, target);
findPath(root.right, target);
list.remove(list.size()-1); //
return paths;
}
0
/ \
1 2
/ \
5 4
遡及法で検索し、解があれば直接戻り、解がなければ前のレイヤに戻ります.
ArrayList<Integer> list = new ArrayList<>(); //
ArrayList<ArrayList<Integer>> paths = new ArrayList<>(); //
public ArrayList<ArrayList<Integer>> findPath(TreeNode root, int target) {
if (root == null) return paths;
list.add(root);
target -= root.val;
if (target == 0 && root.left == null && root.right == null) {
paths.add(new ArrayList<Integer>(list)); // ，
}
findPath(root.left, target);
findPath(root.right, target);
list.remove(list.size()-1); //
return paths;
}