每天一道算法题9

【最大路径和】给定一个二叉树的头节点head，路径的规定有以下三种不同的规定：
1） 路径必须是头节点出发，到叶节点结束，返回最大路径和
2） 路径可以从任意节点出发，但必须往下走到达任何节点，返回最大路径和
3） 路径可以从任意节点出发，到任何节点，返回最大路径和

解答1:
最大路径和 = 每条路径走到叶节点的最大路径和，所以每次往下走，走到叶节点，和之前最大的路径和比较。
路径和 = 当前的节点 + 之前的路径和。

public class Node {
    public int value;
    public Node(int val) {
        value = val;
    }
}

publilc static int maxPath(Node head) {
    p(head, 0);
    return maxSum;
}

public static int maxSum = Integer.MIN_VALUE;

//之前的路径和为pre
public static void p(Node x, int pre) {
    if (x.left == null && x.right == null) {
        maxSum = Math.max(maxSum, pre + x.value);
    }
    if (x.left != null) {
        p(x.left, x.value + pre);
    }

    if (x.right != null) {
        p(x.right, x.value + pre);
    }
}

解答2:
因为是从任意节点出发且只能往下，所以有可能与头节点有关，有可能与头节点无关。
所以就会有五种情况：
1）与头节点无关：1. 自己左子树上的整体最大路径和。2. 自己右子树上的整体最大路径和

2. 与头节点有关： 3. 自己 4. x往左走 5. x往右走

public class Info {
    public int allTreeMaxSum;
    public int fromHeadMaxSum;

    public Info(int all, int from) {
        this.allTreeMaxSum = all;
        this.fromHeadMaxSum = from;
    }
}

public static Info f(Node x) {
    if (x == null) {
        return null;
    }

    Info leftInfo = f(x.left);
    Info rightInfo = f(x.right);
    int p1 = Integer.MIN_VALUE;
    if (leftInfo != null) {
        p1 = leftInfo.allTreeMaxSum;
    }

    int p2 = Integer.MIN_VALUE;
    if (rightInfo != null) {
        p2 = rightInfo.allTreeMaxSum;
    }   

    int p3 = x.value;
    int p4 = Integer.MIN_VALUE;
    if (leftInfo != null) {
        p4 = x.value + leftInfo.fromHeadMaxSum;
    }

    int p5 = Integer.MIN_VALUE;
    if (rightInfo != null) {
        p5 = x.valule + rightInfo.fromHeadMaxSum;
    }

    int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(p4, p5));

    int fromHeadMaxSum = Math.max(Math.max(p3, p4), p5);
    return new Info(allTreeMaxSum, fromHeadMaxSum);
}

public static int maxSum2(Node head) {
    if (head == null) {
        return 0;
    }
    return p(head).allTreeMaxSum;
}

解答3:
因为是从任意节点到任意节点，所以在问题2的基础上只需要再加一种可能性，即与头节点有关时，最大路径和是x既往左走，又往右走

public static Info f(Node x) {
    if (x == null) {
        return null;
    }

    Info leftInfo = f(x.left);
    Info rightInfo = f(x.right);
    int p1 = Integer.MIN_VALUE;
    if (leftInfo != null) {
        p1 = leftInfo.allTreeMaxSum;
    }

    int p2 = Integer.MIN_VALUE;
    if (rightInfo != null) {
        p2 = rightInfo.allTreeMaxSum;
    }   

    int p3 = x.value;
    int p4 = Integer.MIN_VALUE;
    if (leftInfo != null) {
        p4 = x.value + leftInfo.fromHeadMaxSum;
    }

    int p5 = Integer.MIN_VALUE;
    if (rightInfo != null) {
        p5 = x.valule + rightInfo.fromHeadMaxSum;
    }

    int p6 = Integer.MIN_VALUE;
    if (leftInfo != null && rightInfo != null) {
        p6 = x.value + leftInfo.fromHeadMaxSum + rightInfo.fromHeadMaxSum;
    }

    int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(Math.max(p4, p5), p6));
    int fromHeadMaxSum = Math.max(Math.max(p3, p4), p5);
    return new Info(allTreeMaxSum, fromHeadMaxSum);
}