P158 二叉树的最大路径和

描述#

这个题目说的是，给你一棵不为空的二叉树，你要计算出这棵二叉树中的最大路径和。

对于二叉树中任意两个节点，路径指的是从其中一个节点出发，经过它们的最近公共祖先，然后到达另一个节点的节点序列。另外，单个节点也算一条路径。注意，路径不一定会经过原始二叉树的根节点。

比如说，给你的二叉树是：
 -4
/  \

1    2
/ 

4   8
这棵二叉树中，最大路径和是 13。对应的路径是 4 -> 1 -> 8。
再比如说给你的二叉树是：
1

/   

-2   -4
这棵二叉树中，最大路径和是 1。对应的路径只有一个节点 1。

代码#

public class AlgoCasts {
  
  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  private int max3(int a, int b, int c) {
    return Math.max(a, Math.max(b, c));
  }

  private int maxPathSumFrom(TreeNode root) {
    if (root == null) return 0;
    int leftMax = Math.max(maxPathSumFrom(root.left), 0);
    int rightMax = Math.max(maxPathSumFrom(root.right), 0);
    return root.val + Math.max(leftMax, rightMax);
  }

  // Time: O(n^2), Space: O(n)
  public int maxPathSumBruteForce(TreeNode root) {
    if (root == null) return Integer.MIN_VALUE;
    int leftMax = Math.max(maxPathSumFrom(root.left), 0);
    int rightMax = Math.max(maxPathSumFrom(root.right), 0);
    return max3(
      root.val + leftMax + rightMax,
      maxPathSumBruteForce(root.left),
      maxPathSumBruteForce(root.right)
    );
  }

  private int maxPathSumFromRootAndCompute(TreeNode root, int[] max) {
    if (root == null) return 0;
    int leftMax = Math.max(maxPathSumFromRootAndCompute(root.left, max), 0);
    int rightMax = Math.max(maxPathSumFromRootAndCompute(root.right, max), 0);
    max[0] = Math.max(max[0], root.val + leftMax + rightMax);
    return root.val + Math.max(leftMax, rightMax);
  }

  // Time: O(n), Space: O(n)
  public int maxPathSumOn(TreeNode root) {
    int[] max = new int[]{Integer.MIN_VALUE};
    maxPathSumFromRootAndCompute(root, max);
    return max[0];
  }

}