刷了360多道算法題，我終于頓悟了它的真諦
大家好，我是哪吒。
最近一直在刷算法題，刷華為OD算法題，有諸多好處：
- 比如可以考華為OD崗位，大廠算法崗，待遇直接拉滿，走向人生巔峰。
- 不考也沒關(guān)系，就當(dāng)練習(xí)算法題了，哪吒半年時間刷了360多道題，平均一天六道題，一道題40分鐘，一天刷4個小時？現(xiàn)在一看到算法題，真的有一種靈光乍現(xiàn)的感覺。
希望用我自己瘋狂刷題的勁頭，感染大家，讓大家愛上刷題，順利通過華為OD機試，掌握更多優(yōu)秀的算法。
下面這道題，是很經(jīng)典的深度優(yōu)先搜索dfs算法 + 二叉樹。掌握一道題，精通一類題，沖吧~
一、題目描述
某文件系統(tǒng)中有N個目錄，每個目錄都有一個獨一無二的ID。每個目錄只有一個父目錄，但每個父目錄下可以有零個或者多個子目錄，目錄結(jié)構(gòu)呈樹狀結(jié)構(gòu)。
假設(shè)，根目錄的ID為0，且根目錄沒有父目錄，其他所有目錄的ID用唯一的正整數(shù)表示，并統(tǒng)一編號。
現(xiàn)給定目錄ID和其父目錄ID的對應(yīng)父子關(guān)系表[子目錄ID，父目錄ID]，以及一個待刪除的目錄ID，請計算并返回一個ID序列，表示因為刪除指定目錄后剩下的所有目錄，返回的ID序列以遞增序輸出。
注意：
- 被刪除的目錄或文件編號一定在輸入的ID序列中。
- 當(dāng)一個目錄刪除時，它所有的子目錄都會被刪除。
說人話就是：
輸入m行數(shù)據(jù)，第一個元素是子節(jié)點值，第二個是父節(jié)點值，m行數(shù)據(jù)可以組成一個二叉樹。
最后輸入要刪除的節(jié)點，求二叉樹剩下的節(jié)點值。
例如輸入：
5
8 6
10 8
6 0
20 8
2 6
8
二叉樹就會變?yōu)椋?/p>
6
2 8
10 20
刪除最后的8，輸出6 2就是結(jié)果。
很簡單吧，少年~
二、輸入描述
輸入的第一行為父子關(guān)系表的長度m;
接下來的m行為m個父子關(guān)系對;
最后一行為待刪除的ID。序列中的元素以空格分割。
三、輸出描述
輸出一個序列，表示因為刪除指定目錄后，剩余的目錄ID。
四、深度優(yōu)先搜索dfs
1、搜索的要點：
- 初始狀態(tài)。
- 重復(fù)產(chǎn)生新狀態(tài)。
- 檢查新狀態(tài)是否為目標(biāo)，是結(jié)束，否轉(zhuǎn)（2）。
如果搜索是以接近起始狀態(tài)的程序依次擴展?fàn)顟B(tài)的，叫寬度優(yōu)先搜索。
2、如果擴展是首先擴展新產(chǎn)生的狀態(tài)，則叫深度優(yōu)先搜索。
深度優(yōu)先搜索用一個數(shù)組存放產(chǎn)生的所有狀態(tài)。
- 把初始狀態(tài)放入數(shù)組中，設(shè)為當(dāng)前狀態(tài)。
- 擴展當(dāng)前的狀態(tài)，產(chǎn)生一個新的狀態(tài)放入數(shù)組中，同時把新產(chǎn)生的狀態(tài)設(shè)為當(dāng)前狀態(tài)。
- 判斷當(dāng)前狀態(tài)是否和前面的重復(fù)，如果重復(fù)則回到上一個狀態(tài)，產(chǎn)生它的另一狀態(tài)。
- 判斷當(dāng)前狀態(tài)是否為目標(biāo)狀態(tài)，如果是目標(biāo)，則找到一個解答，結(jié)束算法。
- 如果數(shù)組為空，說明無解。
3、深度優(yōu)先搜索dfs代碼架構(gòu)：
public int def(int x, int y ,int step){
if(遞歸出口/達(dá)到目標(biāo)狀態(tài)){
//進(jìn)行對應(yīng)操作
return 0;
}
for (int i = 0; i < n; i++) {
//遍歷剩下的所有的情況
if(visit[i]==0){
//未訪問
x = 下一步更新;
y = 下一步更新;
visit[i] = 1;
def(x,y,step);
visit[i] = 0; //記得回溯還原
}
}
}五、解題思路
根據(jù)題目描述，輸入數(shù)據(jù)可以組成一個二叉樹，如果將某個節(jié)點刪除，求剩余節(jié)點。
輸入父子關(guān)系表的長度m。
接下來的m行輸入父子關(guān)系。
輸入待刪除的ID。
遍歷m個父子關(guān)系，拼接成二叉樹，拼接剩余的目錄ID。
- 如果該關(guān)系的父節(jié)點是value。
- 如果該父節(jié)點不是待移除的ID。
- 拼接成二叉樹。
- 拼接剩余的目錄ID -- builder。
- 移除滿足條件的父子關(guān)系。
- 父子關(guān)系集合treeList移除某節(jié)點，treeList長度-1，下一個坐標(biāo)i也應(yīng)該-1。
- 如果剩余的父子關(guān)系集合treeList為0，則不需要再進(jìn)行dfs，如果要dfs的node節(jié)點是null，則不需要再尋找其左右子節(jié)點；
- 遍歷treeList，拼接二叉樹。
在剩余的父子關(guān)系集合treeList中尋找父節(jié)點是node.left的節(jié)點，進(jìn)行樹的再次拼接。
在剩余的父子關(guān)系集合treeList中尋找父節(jié)點是node.right的節(jié)點，進(jìn)行樹的再次拼接。
輸出符合條件的目錄ID。
六、Java算法源碼
public class OdTest04 {
static Node rootNode = null;
static int removeValue = 0;
// 剩余的目錄ID
static StringBuilder builder = new StringBuilder();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 父子關(guān)系表的長度m
int m = Integer.valueOf(sc.nextLine());
// m個父子關(guān)系
List<int[]> treeList = new ArrayList<>();
for (int i = 0; i < m; i++) {
int[] treeArr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
if(treeArr[1] == 0){
rootNode = new Node(treeArr[0]);
// 拼接二叉樹根ID
builder.append(treeArr[0]).append(" ");
continue;
}
treeList.add(treeArr);
}
// 待刪除的ID
removeValue = Integer.valueOf(sc.nextLine());
/**
* 遍歷m個父子關(guān)系，拼接成二叉樹，拼接剩余的目錄ID
*/
dfs(treeList,rootNode);
builder.deleteCharAt(builder.length() - 1);
// 輸出符合條件的目錄ID
System.out.println(builder);
}
/**
* 深度優(yōu)先搜索dfs
* @param treeList
* @param node
*/
private static void dfs(List<int[]> treeList, Node node){
/**
* 如果剩余的父子關(guān)系集合treeList為0，則不需要再進(jìn)行dfs
* 如果要dfs的node節(jié)點是null，則不需要再尋找其左右子節(jié)點
*/
if(treeList.size() == 0 || node == null){
return;
}
for (int i = 0; i < treeList.size(); i++) {
// 父子關(guān)系
int[] treeArr = treeList.get(i);
// 如果該關(guān)系的父節(jié)點是value
if(treeArr[1] == node.value){
// 如果該父節(jié)點不是待移除的ID
if(removeValue != node.value) {
int sonValue = treeArr[0];
// 如果該子節(jié)點不是待移除的ID
if(removeValue != sonValue){
// 拼接成二叉樹
if(node.left == null){
node.left = new Node(sonValue);
}else if(node.right == null){
node.right = new Node(sonValue);
}
// 拼接剩余的目錄ID
builder.append(sonValue).append(" ");
}
}
// 移除滿足條件的父子關(guān)系
treeList.remove(treeArr);
// 父子關(guān)系集合treeList移除某節(jié)點，treeList長度-1，下一個坐標(biāo)i也應(yīng)該-1
i--;
}
}
// 在剩余的父子關(guān)系集合treeList中尋找父節(jié)點是node.left的節(jié)點，進(jìn)行樹的再次拼接
dfs(treeList,node.left);
// 在剩余的父子關(guān)系集合treeList中尋找父節(jié)點是node.right的節(jié)點，進(jìn)行樹的再次拼接
dfs(treeList,node.right);
}
}七、效果展示
1、輸入
8
6 0
4 6
5 4
7 4
8 6
9 8
10 8
11 10
8
2、輸出
6 4 5 7
3、說明
輸入可以組成二叉樹：
6
4 8
5 7 9 10
11刪除值為8的節(jié)點，變?yōu)? 4 5 7。
4、也許很多人會問，如果節(jié)點的值相等，怎么辦？
8
6 0
4 6
5 4
5 4
5 6
5 5
10 5
11 10
5
5、輸出
6 4
6、說明
輸入可以組成二叉樹：
6
4 5
5 5 5 10
11刪掉值為5的節(jié)點，變?yōu)? 4。
