輸入一顆二叉樹的根節點和一個整數，按字典序列印出二叉樹中結點值的和為輸入整數的所有路徑，路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑
解題思路
使用遞回可以解決這個問題：
- 前序遞回遍歷樹，途中把結點加入路徑
- 如果遍歷到葉子結點，則比較當前路徑的和是否符合預期值
- 符合條件，將當前路徑加入結果集
- 不符合條件，不作任何操作
- 因為使用的是前序遍歷，所以每一輪遞回都會回傳父結點，所以當前保存路徑也應該彈出當前結點
public class Solution {
// 用來保存所有符合條件的路徑
private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
// 路徑
private ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null) {
return listAll;
}
findPath(root, target);
return listAll;
}
public void findPath(TreeNode node, int target) {
// 先將當前值放入路徑
list.add(node.val);
target -= node.val;
// 如果當前結點已經是葉子結點，并且符合條件，則將當前路徑加入結果集
if(target == 0 && node.left == null && node.right == null) {
listAll.add(new ArrayList<>(list));
}
// 繼續向左子樹遍歷
if(node.left != null) {
findPath(node.left, target);
}
// 繼續向右子樹遍歷
if(node.right != null) {
findPath(node.right, target);
}
// 本輪結束，從路徑中彈出當前結點
list.remove(list.size() - 1);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/166810.html
標籤：其他
上一篇：二叉搜索樹的后序遍歷序列
下一篇：復雜鏈表的復制