Leetcode 124. Binary Tree Maximu

Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,
1
/ |
2 3
Return 6.

题意：求一个二叉树的一条最大路径和，这条路径可以从任意节点起始，到任意节点结束，但至少要有一个节点。

思路：
如例子，路径总共有三种类型：[1,2]，[1,3]，[2,1,3]。
即每个节点可以连接它的左边一条最大路径，或连接右边一条最大路径，或把左右最大路径连接起来。
因此我想到，用一个方法求以当前节点为起始节点，到它下方任意节点为终点的最长路径。通过这个方法可以求一个节点左右的最长路径和，然后和这个节点值相加，就是以这个节点作为顶点的最大路径。遍历树中所有节点，就可以找到最大的路径和。

public int maxPath = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    if (root == null) {
        return 0;
    }

    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode cur = q.poll();
        int left = helper(cur.left);
        int right = helper(cur.right);
        maxPath = Math.max(maxPath, left + cur.val + right);
        if (cur.left != null) {
            q.offer(cur.left);
        }
        if (cur.right != null) {
            q.offer(cur.right);
        }
    }

    return maxPath;
}

public int helper(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = helper(root.left);
    int right = helper(root.right);

    int curMax = Math.max(left, right) + root.val;
    return curMax > 0 ? curMax : 0;
}

这个方法，可以通过，但是会超时。原因是每层都遍历一次，那么树下方的节点要重复调用helper很多次。
优化：helper中已经得到了一个节点左右单向最大路径和，那么就可以在helper中直接求出以当前节点为顶点的最大路径和。即把maxPath更新的那行代码移到helper中，这样每个节点只会被遍历一次。

public int maxPath = Integer.MIN_VALUE;

public int maxPathSum1(TreeNode root) {
    if (root == null) {
        return 0;
    }

    helper(root);

    return maxPath;
}

public int helper1(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int left = helper(root.left);
    int right = helper(root.right);
    maxPath = Math.max(maxPath, root.val + left + right);
    int curMax = Math.max(left, right) + root.val;
    return curMax > 0 ? curMax : 0;
}