二叉树中的最大路径和「变题」

124. 二叉树中的最大路径和

开头先来一个小插曲，关于「二叉树路径」相关的总结可见 二叉树路径相关技巧

private int ans = -1000;
public int maxPathSum(TreeNode root) {
    f(root);
    return ans;
}
private int f(TreeNode root) {
    if (root == null) return 0;
    int l = f(root.left);
    int r = f(root.right);
    ans = Math.max(ans, Math.max(0, l) + Math.max(0, r) + root.val);
    return Math.max(0, Math.max(Math.max(0, l), Math.max(0, r))) + root.val;
}

变题一：输出最大路径

​x
class Solution {
    private int ans = -1000;
    private List<Integer> path = new ArrayList<>();
    public int maxPathSum(TreeNode root) {
        f(root);
        System.out.println(path);
        return ans;
    }
    private Pair f(TreeNode root) {
        Pair cur = new Pair(0, new ArrayList<>());
        if (root == null) return cur;
        Pair l = f(root.left);
        Pair r = f(root.right);
        if (l.sum < 0) l = new Pair(0, new ArrayList<>());
        if (r.sum < 0) r = new Pair(0, new ArrayList<>());
        int sum = l.sum + r.sum + root.val;
        if (ans < sum) {
            ans = sum;
            path = new ArrayList<>();
            path.addAll(l.path);
            path.add(root.val);
            path.addAll(r.path);
        }

        if (l.sum > r.sum) {
            cur.sum = l.sum + root.val;
            cur.path.addAll(l.path);
            cur.path.add(root.val);
        } else {
            cur.sum = r.sum + root.val;
            cur.path.add(root.val);
            cur.path.addAll(r.path);
        }

        return cur;
    }
}
class Pair {
    int sum;
    List<Integer> path;
    public Pair(int sum, List<Integer> path) {
        this.sum = sum;
        this.path = path;
    }
}

变题二：相邻字符不同的最长路径

题目详情可见 相邻字符不同的最长路径

xxxxxxxxxx
private int ans = 1;
private char[] s;
private List<Integer>[] tree;
public int longestPath(int[] parent, String S) {
    s = S.toCharArray();
    tree = new ArrayList[parent.length];
    Arrays.setAll(tree, e -> new ArrayList<>());
    for (int i = 1; i < parent.length; i++) {
        tree[parent[i]].add(i);
    }
    f(0);
    return ans;
}
private int[] f(int v) {
    int c = s[v] - 'a';
    int[] res = new int[]{1, c};
    if (tree[v].size() == 0) return res;
    Queue<int[]> q = new PriorityQueue<>((a, b) -> b[0] - a[0]);
    for (int next : tree[v]) {
        q.offer(f(next));
    }
    int sum = 1, cnt = 0;
    while (!q.isEmpty() && cnt < 2) {
        int[] cur = q.poll();
        if (cur[1] != c && cnt < 1) {
            res[0] += cur[0];
            sum += cur[0];
            cnt++;
        } else if (cur[1] != c && cnt < 2) {
            sum += cur[0];
            cnt++;
        }
    }
    ans = Math.max(ans, sum);
    return res;
}