JZ34 二叉樹中和為某一值的路徑(二)
描述
輸入一顆二叉樹的根節點root和一個整數expectNumber，找出二叉樹中結點值的和為expectNumber的所有路徑，
1.該題路徑定義為從樹的根結點開始往下一直到葉子結點所經過的結點
2.葉子節點是指沒有子節點的節點
3.路徑只能從父節點到子節點，不能從子節點到父節點
4.總節點數目為n
思路
當前的路徑path要更新
當前的目標值expectNumber要迭代，減去當前節點的值
若當前節點是葉子節點，考慮是否滿足路徑的期待值，并考慮是否將路徑添加到回傳串列中
具體做法：
step 1：維護兩個向量ret和path
step 2：撰寫遞回函式dfs
step 3：遞回函式內部要處理更新path，更新expectNumber，判斷是否為葉子節點和判斷是否要將path追加到ret末尾
代碼
package mid.JZ34二叉樹中和為某一值的路徑2;
import java.util.ArrayList;
import java.util.LinkedList;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
dfs(root,expectNumber);
return ret;
}
public void dfs(TreeNode root, int expectNumber) {
if (root == null) {
return;
}
path.add(root.val);
expectNumber -= root.val;
if (root.left == null && root.right == null && expectNumber == 0) {
ret.add(new ArrayList<>(path));
}
dfs(root.left, expectNumber);
dfs(root.right, expectNumber);
path.removeLast();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/539295.html
標籤：Java