树的直径

• OI Wiki: https://oi-wiki.org/graph/tree-diameter/

题目	难度
543. 二叉树的直径	简单
$1245. 树的直径	中等	树形 DP
$1522. N 叉树的直径	中等
2246. 相邻字符不同的最长路径	困难	树形 DP

定义

树上任意两节点之间最长的简单路径即为树的「直径」。

可以用两次 DFS 或者树形 DP 的方法在 时间求出树的直径。

543. 二叉树的直径

public class Solution543 {
    private int max = 1;

    public int diameterOfBinaryTree(TreeNode root) {
        max = 1;
        dfs(root);
        return max - 1;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        max = Math.max(max, left + right + 1);
        return Math.max(left, right) + 1;
    }
}

$1522. N 叉树的直径

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Solution1522 {
    private int max = 1;

    public int diameter(Node root) {
        max = 1;
        dfs(root);
        return max - 1;
    }

    private int dfs(Node root) {
        if (root == null) {
            return 0;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());
        for (Node child : root.children) {
            int cnt = dfs(child);
            priorityQueue.add(cnt);
        }
        int top1 = priorityQueue.isEmpty() ? 0 : priorityQueue.remove();
        int top2 = priorityQueue.isEmpty() ? 0 : priorityQueue.remove();
        max = Math.max(max, top1 + top2 + 1);
        return Math.max(top1, top2) + 1;
    }

    static class Node {
        public int val;
        public List<Node> children;


        public Node() {
            children = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            children = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _children) {
            val = _val;
            children = _children;
        }
    }
}

树形 DP

$1245. 树的直径

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution1245 {
    private Map<Integer, List<Integer>> graph;
    private int ans;
    int n;
    private boolean[] visited;

    public int treeDiameter(int[][] edges) {
        // n 个点
        n = edges.length + 1;
        visited = new boolean[n];
        ans = 0;
        graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], key -> new ArrayList<>()).add(edge[1]);
            graph.computeIfAbsent(edge[1], key -> new ArrayList<>()).add(edge[0]);
        }

        visited[0] = true;
        dfs(0);
        return ans;
    }

    private int dfs(int x) {
        if (x > n) {
            return 0;
        }
        int maxLen = 0;
        for (int y : graph.getOrDefault(x, new ArrayList<>())) {
            if (!visited[y]) {
                visited[y] = true;
                int len = dfs(y) + 1;
                ans = Math.max(ans, maxLen + len);
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }
}

2246. 相邻字符不同的最长路径

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution2246 {
    private String s;
    private Map<Integer, List<Integer>> graph;
    private int ans;

    public int longestPath(int[] parent, String s) {
        int n = parent.length;

        this.s = s;
        graph = new HashMap<>();
        ans = 0;

        for (int i = 1; i < n; i++) {
            graph.computeIfAbsent(parent[i], key -> new ArrayList<>()).add(i);
        }
        dfs(0);
        return ans + 1;
    }

    private int dfs(int x) {
        int maxLen = 0;
        for (int y : graph.getOrDefault(x, new ArrayList<>())) {
            int len = dfs(y) + 1;
            if (s.charAt(y) != s.charAt(x)) {
                ans = Math.max(ans, maxLen + len);
                maxLen = Math.max(maxLen, len);
            }
        }
        return maxLen;
    }
}

（全文完）