1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    private int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxSum(root);
        return max;
    }

    private int maxSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftTreeMaxSum = Math.max(maxSum(node.left), 0);
        int rightTreeMaxSum = Math.max(maxSum(node.right), 0);
        max = Math.max(max, node.val + leftTreeMaxSum + rightTreeMaxSum);
        return Math.max(leftTreeMaxSum + node.val, rightTreeMaxSum + node.val);
    }
}

这个题很有意思是分解问题型递归 + 回溯类型的递归的结合. 递归函数的功能就是告诉我们某个tree从root往下走能组成的最大的sum, 必须包含root. 同时这个递归函数还能带我们去各个node, 这样我们在一个node后看如果该node作为path中的一员, 能组成的max最大是多少. 走遍每一个node, 这样全局的max就能得到了.

时间复杂度: O(n)
空间复杂度: O(n)