乐趣区

关于后端:树形-DP树形-DP-的通用思路

题目形容

这是 LeetCode 上的 310. 最小高度树 ,难度为 中等

Tag :「树形 DP」、「DFS」、「动静布局」

树是一个无向图,其中任何两个顶点只通过一条门路连贯。换句话说,一个任何没有简略环路的连通图都是一棵树。

给你一棵蕴含 $n$ 个节点的树,标记为 $0$ 到 $n – 1$。给定数字 $n$ 和一个有 $n – 1$ 条无向边的 edges 列表(每一个边都是一对标签),其中 $edges[i] = [a_i, b_i]$ 示意树中节点 $a_i$ 和 $b_i$ 之间存在一条无向边。

可抉择树中任何一个节点作为根。当抉择节点 $x$ 作为根节点时,设后果树的高度为 $h$。在所有可能的树中,具备最小高度的树(即,min(h))被称为 最小高度树。

请你找到所有的 最小高度树 并按 任意程序 返回它们的根节点标签列表。

树的 高度 是指根节点和叶子节点之间最长向下门路上边的数量。

示例 1:

输出:n = 4, edges = [[1,0],[1,2],[1,3]]

输入:[1]

解释:如图所示,当根是标签为 1 的节点时,树的高度是 1,这是惟一的最小高度树。

示例 2:

输出:n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]

输入:[3,4]

提醒:

  • $1 <= n <= 2 \times 10^4$
  • $edges.length = n – 1$
  • $0 <= ai, bi < n$
  • $ai != bi$
  • 所有 $(ai, bi)$ 互不雷同
  • 给定的输出保障是一棵树,并且不会有反复的边

树形 DP

这是一道树形 DP 模板题。

当确定以某个点为根节点时,整棵树的状态惟一固定,无妨以编号为 $0$ 的节点作为根节点进行剖析。

假如以后解决到的节点为 u,其是从父节点 fa 遍历而来,且将要遍历的子节点为 j

即树的状态如图所示(一些可能有的出边用虚线示意):

树形 DP 问题通常将问题依据「方向」进行划分。

对于以后解决到的节点 u 而言,咱们依据是否思考「从 fau 的出边」将其分为「往上」和「往下」两个方向。

假如咱们能够通过 DFS 预处理出 $f$ 数组和 $g$ 数组:

  • $f[u]$ 代表在以 $0$ 号点为根节点的树中,以 u 节点为子树根节点时,往下的最大高度
  • $g[u]$ 代表在以 $0$ 号点为根节点的树中,以 u 节点为子节点时,往上的最大高度

那么最终以 u 为根节点的最大高度为 $\max(f[u], g[u])$。

$f[u]$ 只须要简略的 DFS 即可解决进去。对于 $g[u]$ 而言,其同样蕴含「往上」和「往下」两局部:

  • 对于通过 fa 后接着往上的局部有 $g[fa] + 1$
  • 对于通过 fa 后转而往下的局部,咱们须要思考「fa 节点往下的最大值 $f[fa]$」是否由 u 节点参加而来进行分状况探讨:

    • 如果 $f[fa]$ 自身不禁 u 参加,那么 $g[u]$ 该当是 fa 节点往下的最大值 $+1$ 而来($+1$ 代表加上 fau 的边)
    • 如果自身 fa 往下的最大值由 u 节点参加,此时该当应用 fa 往下的次大值 $+1$ 来更新 $g[u]$

因而咱们须要对 $f$ 数组进行拆分,拆分为记录「最大值的 $f1$ 数组」和记录「次大值的 $f2$ 数组(留神这里的次大值是非严格的次大值)」,同时应用 $p$ 数组记录下获得 $f1[u]$ 时 u 的子节点 j 为何值。

实现上,在解决「往上」方向的 DFS 时,为防止对 fa 节点为空的解决,咱们能够将「用 fa 来更新 u」调整为「用 u 来更新 j」。

代码:

class Solution {
    int N = 20010, M = N * 2, idx = 0;
    int[] he = new int[N], e = new int[M], ne = new int[M];
    int[] f1 = new int[N], f2 = new int[N], g = new int[N], p = new int[N];
    void add(int a, int b) {e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {Arrays.fill(he, -1);
        for (int[] e : edges) {int a = e[0], b = e[1];
            add(a, b); add(b, a);
        }
        dfs1(0, -1);
        dfs2(0, -1);
        List<Integer> ans = new ArrayList<>();
        int min = n;
        for (int i = 0; i < n; i++) {int cur = Math.max(f1[i], g[i]);
            if (cur < min) {
                min = cur;
                ans.clear();
                ans.add(i);
            } else if (cur == min) {ans.add(i);
            }
        }
        return ans;
    }
    int dfs1(int u, int fa) {for (int i = he[u]; i != -1; i = ne[i]) {int j = e[i];
            if (j == fa) continue;
            int sub = dfs1(j, u) + 1;
            if (sub > f1[u]) {f2[u] = f1[u];
                f1[u] = sub;
                p[u] = j;
            } else if (sub > f2[u]) {f2[u] = sub;
            }
        }
        return f1[u];
    }
    void dfs2(int u, int fa) {for (int i = he[u]; i != -1; i = ne[i]) {int j = e[i];
            if (j == fa) continue;
            if (p[u] != j) g[j] = Math.max(g[j], f1[u] + 1);
            else g[j] = Math.max(g[j], f2[u] + 1);
            g[j] = Math.max(g[j], g[u] + 1);
            dfs2(j, u);
        }
    }
}
  • 工夫复杂度:$O(n)$
  • 空间复杂度:$O(n)$

补充

可能会首次接触「树形 DP」的同学不太了解,这里再补充阐明一下。

归根结底,以 u 为根节点的最大深度,必然是上面三种状况之一(往下、往上 和 往上再往下)。

其中对 $f$ 数组的拆分(变为 $f1$ 和 $f2$)以及记录获得 $f1$ 对应的子节点 $p[i]$,目标都是为了可能正确统计「往上再往下」的状况(统计该状况时,不能思考从 fa 通过 u 的门路,因而须要记录一个非严格的次大值 $f2$)。

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.310 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。

在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

退出移动版