124. Binary Tree Maximum Path Sum ------H

Given a non-empty 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.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

A:
 ---------------------------------3rd   pass ----

传递一个可以引用的参数来记录最大的值。

返回的是该节点向下的最大值(最少一个节点)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int maxRes = INT_MIN;
        helper(root, maxRes);
        return maxRes;
    }
private:
    int helper(TreeNode* root, int & maxRes){
        if(not root)
            return 0;        
        int maxLeft = helper(root->left, maxRes);
        int maxRight = helper(root->right, maxRes);   
        int maxAtRoot = root->val + max(0, maxLeft) + max(0,maxRight);
        maxRes = max(maxRes, maxAtRoot);
        return root->val + max(0, max(maxLeft, maxRight) );
    }
};

或者我们允许左或右子树，可以没有节点。

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int maxRes = INT_MIN;
        helper(root, maxRes);
        return maxRes;
    }
private:
    int helper(TreeNode* root, int & maxRes){
        if(not root)
            return 0;        
        int maxLeft = helper(root->left, maxRes);
        int maxRight = helper(root->right, maxRes);   
        int maxAtRoot = root->val + maxLeft + maxRight;
        maxRes = max(maxRes, maxAtRoot);
        return max(0, root->val + max(maxLeft, maxRight) );
    }
};

 -------------------------------------1 st round -----------------------------------------
很简单的思路：
 因为，必须有一个节点作为root（最少选一个节点，只要树不空，就不能不选） 。  那么，也就有且只有一个节点。  我们因此，只需要检测，通过每一节点的最大path sum 就可以了。

public class BinaryTreeMaximumPathSum {
    // Improvement : record the maxPathDown value of each node;
    // in this way, we need to build another treeNode class to record maxValue
    // NOTE: the hidden philosophy is : we have only one
    public int maxPathSum(TreeNode root) {
        // recursively calling, to build the new tree
        TreeNode2 root2 = buildTree2(root);
        // traversal root2, to find the max path rooted at each node
        int[] res = new int[1];
        res[0] = Integer.MIN_VALUE;
        getMaxPathSum(root2, res);
        return res[0];
    }

    private void getMaxPathSum(TreeNode2 root, int[] res) {// root must be
                                                            // included
        // get the max paths sum at root, and then search child
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            int curPathSum = root.maxPathUpHere;
            res[0] = Math.max(res[0], curPathSum);
            return;
        }
        if (root.left != null && root.right == null) {
            res[0] = Math.max(res[0], root.maxPathUpHere);
            getMaxPathSum(root.left, res);
            return;
        }

        if (root.left == null && root.right != null) {
            res[0] = Math.max(res[0], root.maxPathUpHere);
            getMaxPathSum(root.right, res);
            return;
        }
        // NOW, both children are not null
        int curPathSum = root.val + Math.max(0, root.right.maxPathUpHere)
                + Math.max(0, root.left.maxPathUpHere);
        res[0] = Math.max(res[0], curPathSum);
        getMaxPathSum(root.left, res);
        getMaxPathSum(root.right, res);
        return;
    }

    private TreeNode2 buildTree2(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode2 root2 = new TreeNode2(root);
        root2.left = buildTree2(root.left);
        root2.right = buildTree2(root.right);
        int maxLeft = 0;
        if (root2.left != null && root2.left.maxPathUpHere > 0)// we can do not
                                                                // count it
            maxLeft = root2.left.maxPathUpHere;
        int maxRight = 0;
        if (root2.right != null && root2.right.maxPathUpHere > 0)
            maxRight = root2.right.maxPathUpHere;
        root2.maxPathUpHere = root2.val + Math.max(maxLeft, maxRight);
        return root2;
    }

    class TreeNode2 {
        int val;
        TreeNode2 left, right;
        int maxPathUpHere = 0; // max sum to to current node

        TreeNode2(TreeNode node) {
            val = node.val;
        }
    }
}

------------------第二遍， 不用重新创立一个tree----------- 就直接更改原有的treeNode.val-----
方法就是传递，并返回一个数组 因此，对一个TreeNode nodeA 检测的时候，我们要返回
 int res[] = new int[2]
res[0] :  maximim path sum,  up to nodeA (inclusive)   or 0 ( if former < 0）
res[1] : maximim path sum , rooted at nodeA ( inclusive)

public class Solution {
    public int maxPathSum(TreeNode root) {
        int[ ] res = getMaxPathSum(root);
        return res[1];
    }

    private int[] getMaxPathSum(TreeNode root){
        // res[0] is the up-to-node max-sum, current node must be included
        // res[1] is the max-sum of a tree, rooted this node
        int[] res = { Integer.MIN_VALUE, Integer.MIN_VALUE };
        if (root == null)
            return res;
        int[] left = getMaxPathSum(root.left);
        int[] right = getMaxPathSum(root.right);
        res[0] = root.val + Math.max(0, Math.max(left[0], right[0]));
        int maxOfChild = Math.max(left[1], right[1]);// max sum of path
        int maxSumThroughRoot = Math.max(0,left[0]) + root.val + Math.max(0, right[0]);
        res[1] =    Math.max(maxOfChild, maxSumThroughRoot);
        return res;
    }
}

Mistakes:

1：  必须找到一条路径，不能不找。    --------->



Learned：
1: leetcode的run time error 多为：
1）print了东西
2） 99%是你deference null pointer了，
     endless loop则会提示Time limit exceeded。
3）数组越界，除0，爆栈，访问空地址
4)  leetcode中，不好用static int 来存储变量。 那么，我们可以声明一个数组， int res[] = int [1].  然后，就传这个数组就可以了。