企业官网建设流程全解析

哪里有免费的网站模板下载 迅雷下载 迅雷下载软件,广告公司接单软件,带商城的wordpress,怎么把网站封包做app834. 树中距离之和 问题描述 给定一个有 n 个节点的无向树#xff0c;节点编号从 0 到 n-1。给你一个长度为 n-1 的二维数组 edges#xff0c;其中 edges[i] [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。 返回一个长度为 n 的数组 answer#xff0c;其中 answer[i] 是…834. 树中距离之和问题描述给定一个有n个节点的无向树节点编号从0到n-1。给你一个长度为n-1的二维数组edges其中edges[i] [ai, bi]表示树中节点ai和bi之间存在一条边。返回一个长度为n的数组answer其中answer[i]是树中所有其他节点到节点i的距离之和。示例输入:n6,edges[[0,1],[0,2],[2,3],[2,4],[2,5]]输出:[8,12,6,10,10,10]节点0到其他节点的距离1→1, 2→1, 3→2, 4→2, 5→2总和8节点1到其他节点的距离0→1, 2→2, 3→3, 4→3, 5→3总和12节点2到其他节点的距离0→1, 1→2, 3→1, 4→1, 5→1总和6以此类推算法思路两次DFS树形DP核心如果暴力计算每个节点到其他所有节点的距离时间复杂度为 O(n²)利用树的结构可以通过换根DP优化到 O(n)第一次DFS后序遍历以任意节点如0为根计算subtreeSize[node]以node为根的子树中节点数量dp[node]子树中所有节点到node的距离之和第二次DFS前序遍历利用父节点的结果推导子节点的结果当从父节点u移动到子节点v时v的子树中的subtreeSize[v]个节点距离减少1其他n - subtreeSize[v]个节点距离增加1answer[v] answer[u] - subtreeSize[v] (n - subtreeSize[v])answer[v] answer[u] n - 2 * subtreeSize[v]代码实现importjava.util.*;classSolution{privateListListIntegergraph;// 邻接表表示树privateint[]subtreeSize;// subtreeSize[i] 表示以i为根的子树节点数privateint[]dp;// dp[i] 表示子树中所有节点到i的距离之和privateint[]answer;// 最终答案privateintn;// 节点总数/** * 计算树中每个节点到其他所有节点的距离之和 * 使用两次DFS的换根DP * * param n 节点数量 * param edges 边数组 * return 每个节点的距离和数组 */publicint[]sumOfDistancesInTree(intn,int[][]edges){this.nn;this.graphnewArrayList();this.subtreeSizenewint[n];this.dpnewint[n];this.answernewint[n];// 初始化邻接表for(inti0;in;i){graph.add(newArrayList());}// 构建无向图for(int[]edge:edges){graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);}// 第一次DFS以0为根计算子树大小和dp值dfs1(0,-1);// 第二次DFS换根计算所有节点的答案dfs2(0,-1);returnanswer;}/** * 第一次DFS后序遍历 * 计算每个节点的子树大小和子树内距离和 * * param node 当前节点 * param parent 父节点避免回溯 */privatevoiddfs1(intnode,intparent){subtreeSize[node]1;// 至少包含自己dp[node]0;// 初始化距离和为0// 遍历所有子节点for(intchild:graph.get(node)){if(childparent){continue;// 跳过父节点}dfs1(child,node);// 递归处理子树// 累加子树信息subtreeSize[node]subtreeSize[child];// 子树中每个节点到当前节点的距离 到子节点的距离 1// 总距离 dp[child] subtreeSize[child]dp[node]dp[child]subtreeSize[child];}}/** * 第二次DFS前序遍历 * * param node 当前节点 * param parent 父节点 */privatevoiddfs2(intnode,intparent){// 当前节点的答案就是dp[node]第一次DFS已计算根节点答案answer[node]dp[node];// 遍历所有子节点进行换根for(intchild:graph.get(node)){if(childparent){continue;// 跳过父节点}// 换根从node移动到child// 保存原始值intoriginalSubtreeSizeNodesubtreeSize[node];intoriginalSubtreeSizeChildsubtreeSize[child];intoriginalDpNodedp[node];intoriginalDpChilddp[child];// 更新子树大小换根后subtreeSize[node]n-subtreeSize[child];subtreeSize[child]n;// 更新dp值answer[child] answer[node] n - 2 * subtreeSize[child]换根前的值dp[child]dp[node]-subtreeSize[child](n-subtreeSize[child]);// 递归处理子树dfs2(child,node);}}}算法分析时间复杂度O(n)两次DFS每次遍历所有节点和边一次树有 n-1 条边所以总时间复杂度为 O(n)空间复杂度O(n)邻接表存储O(n)递归栈深度O(n)最坏情况下树退化为链算法过程输入n 6, edges [[0,1],[0,2],[2,3],[2,4],[2,5]]第一次DFS以0为根dfs1(0, -1)处理子节点1dfs1(1, 0)subtreeSize[1] 1,answer[1] 0处理子节点2dfs1(2, 0)dfs1(3, 2)→subtreeSize[3] 1,answer[3] 0dfs1(4, 2)→subtreeSize[4] 1,answer[4] 0dfs1(5, 2)→subtreeSize[5] 1,answer[5] 0subtreeSize[2] 1 1 1 1 4answer[2] (01) (01) (01) 3subtreeSize[0] 1 1 4 6answer[0] (01) (34) 8第一次DFS后subtreeSize [6, 1, 4, 1, 1, 1]answer [8, 0, 3, 0, 0, 0]第二次DFS换根dfs2(0, -1)处理子节点1answer[1] answer[0] 6 - 2 * subtreeSize[1] 8 6 - 2 12dfs2(1, 0)1没有其他子节点处理子节点2answer[2] answer[0] 6 - 2 * subtreeSize[2] 8 6 - 8 6dfs2(2, 0)处理子节点3answer[3] 6 6 - 2 10处理子节点4answer[4] 6 6 - 2 10处理子节点5answer[5] 6 6 - 2 10最终结果answer [8, 12, 6, 10, 10, 10]测试用例importjava.util.Arrays;publicclassMain{publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1标准示例intn16;int[][]edges1{{0,1},{0,2},{2,3},{2,4},{2,5}};int[]result1solution.sumOfDistancesInTree(n1,edges1);System.out.println(Test 1: Arrays.toString(result1));// [8, 12, 6, 10, 10, 10]// 测试用例2两个节点intn22;int[][]edges2{{0,1}};int[]result2solution.sumOfDistancesInTree(n2,edges2);System.out.println(Test 2: Arrays.toString(result2));// [1, 1]// 测试用例3链状树intn34;int[][]edges3{{0,1},{1,2},{2,3}};int[]result3solution.sumOfDistancesInTree(n3,edges3);System.out.println(Test 3: Arrays.toString(result3));// [6, 4, 4, 6]// 测试用例4星形树intn45;int[][]edges4{{0,1},{0,2},{0,3},{0,4}};int[]result4solution.sumOfDistancesInTree(n4,edges4);System.out.println(Test 4: Arrays.toString(result4));// [4, 6, 6, 6, 6]// 测试用例5单节点intn51;int[][]edges5{};int[]result5solution.sumOfDistancesInTree(n5,edges5);System.out.println(Test 5: Arrays.toString(result5));// [0]// 测试用例6三个节点线性intn63;int[][]edges6{{0,1},{1,2}};int[]result6solution.sumOfDistancesInTree(n6,edges6);System.out.println(Test 6: Arrays.toString(result6));// [3, 2, 3]}}关键点换根DP利用已计算的父节点结果快速推导子节点结果避免重复计算将O(n²)优化到O(n)换根公式当根从u移到v时v的子树中subtreeSize[v]个节点距离-1其余n - subtreeSize[v]个节点距离1变化-subtreeSize[v] (n - subtreeSize[v]) n - 2*subtreeSize[v]树使用邻接表存储无向树DFS时通过parent参数避免回溯两次遍历第一次DFS后序自底向上计算子树信息第二次DFS前序自顶向下传播换根结果常见问题为什么第一次DFS后只有根节点正确第一次DFS只计算了子树内的距离和没有考虑父节点方向的节点。只有根节点没有父节点。