大家好，我是哪吒。
最近一直在刷算法题，刷华为OD算法题，有诸多好处：
希望用我自己疯狂刷题的劲头，感染大家，让大家爱上刷题，顺利通过华为OD机试，掌握更多优秀的算法。
下面这道题，是很经典的深度优先搜索dfs算法 + 二叉树。掌握一道题，精通一类题，冲吧~
某文件系统中有N个目录，每个目录都有一个独一无二的ID。每个目录只有一个父目录，但每个父目录下可以有零个或者多个子目录，目录结构呈树状结构。
假设，根目录的ID为0，且根目录没有父目录，其他所有目录的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。
如果搜索是以接近起始状态的程序依次扩展状态的，叫宽度优先搜索。
深度优先搜索用一个数组存放产生的所有状态。
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。
在剩余的父子关系集合treeList中寻找父节点是node.left的节点，进行树的再次拼接。
在剩余的父子关系集合treeList中寻找父节点是node.right的节点，进行树的再次拼接。
输出符合条件的目录ID。
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); }}8
6 0
4 6
5 4
7 4
8 6
9 8
10 8
11 10
8
6 4 5 7
输入可以组成二叉树：
6 4 85 7 9 10 11删除值为8的节点，变为6 4 5 7。
8
6 0
4 6
5 4
5 4
5 6
5 5
10 5
11 10
5
6 4
输入可以组成二叉树：
6 4 55 5 5 10 11删掉值为5的节点，变为6 4。
本文链接：http://www.28at.com/showinfo-26-39503-0.html刷了360多道算法题，我终于顿悟了它的真谛
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com
Copyright © 2016-2023 天津谷骐科技有限公司 版权所有 sitemap.xml
违法及侵权请联系：2376512515@qq.com 津ICP备18001702号
津公网安备 12010102000574号
