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