二叉树中的最大路径和

这一题有点类似一维数组求最大子序列的和，一维最大子序列和从一维的角度判断，这里二叉树有左右子树考虑。
maxpath（root）方法的返回值的意思就是求得root节点到该root子孙的任意一节点的最大路径值（注意区别这里root和根节点root,这里root是递归下去的节点）。在这个函数里还比较了以root为路径节点
if (maxsum < sum)
maxsum = sum;//

int maxsum = Integer.MIN_VALUE;// 初始化为最小值

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

        maxSum(root);
        return maxsum;
    }

    public int maxSum(TreeNode root) {

        if (root == null)
            return 0;
        int left = maxSum(root.left);
        int right = maxSum(root.right);
        int sum = root.val;
        if (left > 0)
            sum += left;
        if (right > 0)
            sum += right;
        if (maxsum < sum)
            maxsum = sum;
        return Math.max(left, right) > 0 ? Math.max(left, right) + root.val : root.val;
    }

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
  /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
  int maxPathSum(TreeNode* root) {
    ans_ = INT_MIN;
    dfs(root);
    return ans_;
  }
  
private:
  int ans_;
  
  int dfs(TreeNode* root) {
    if (!root) return 0;
    const int ls = max(0, dfs(root->left));
    const int rs = max(0, dfs(root->right));
    ans_ = max(ans_, root->val + ls + rs);
    return root->val + max(ls, rs); 
  }
};

class Solution {
    int maxSum = Integer.MIN_VALUE;//-2147483648
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 递归计算左右子节点的最大贡献值只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;
        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);
        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
}

class Solution {
    int ma;
public:
    int maxPathSum(TreeNode *root) {
        ma = 0x80000000;
        int res = search(root);
        res = max(res, ma);
        return res;
        
    }
    int search(TreeNode* root) {
        if(root == NULL) {
            return 0;
        }
        int lh = search(root->left);
        int rh = search(root->right);
        int lst = max(lh, rh);
        //三种情况：1.包含一个子树和顶点，2.仅包含顶点，3.包含左子树和右子树以及顶点。
        int sum = lh + rh + root->val;//情况3
        sum = max(sum, root->val);//情况2
        sum = max(sum, lst + root->val);//情况1
        //取最大值
        if(sum > ma) {
            ma = sum;
        }
        //对于每一个子树，返回包含该子树顶点的深度方向的路径和的最大值。
        int rt = lst + root->val;
        rt = max(rt, root->val);
        return rt;
    }
};

class Solution {
public:
    int maxPathSum(TreeNode *root) {
        if(!root) return 0;
        int maxSum = --65535;//这里的初始值必须设为一个不可能达到的负数 最大值有可能为负的情况
        maxlu(root,maxSum);//递归遍历所有结点的同时时刻更新可能的最大路径值
        return maxSum;
    }
    int maxlu(TreeNode* root, int& maxSum) {
        if(!root) return 0;
        int L = maxlu(root->left,maxSum);
        int R = maxlu(root->right,maxSum);
        if(root->val>maxSum) maxSum = root->val;
        if((L+R+root->val)>maxSum) maxSum = L+R+root->val;
        int curVal =  L > R ? L + root->val : R + root->val;
        if(curVal>maxSum) maxSum = curVal;
        if(curVal > 0) return curVal; //只有大于0的分支路径是需要的否则只会降低当前最大值 
        else return 0;
    }
};

    int res = -1008611;
    public int maxPathSum (TreeNode root) {
        // write code here
        dfs(root);
        return res;
    }
    public int dfs(TreeNode root) {
        if(root == null) return 0;
        //计算该节点左右子树的大小，大于0的为正收益，小于0的就不要了
        int left = Math.max(dfs(root.left), 0);
        int right = Math.max(dfs(root.right), 0);
        //算上根节点的收益
        int sum = left + right + root.val;
        //更新结果
        res = Math.max(res, sum);
        //返回最大收益
        return root.val + Math.max(left, right);
    }

class Solution {
    /**
     *  问题分解，求树的最大路径，递归树的节点
     *  有三种可能：
     *    1. 最大路径经过该节点本身从左子树到右子树
     *    2. 最大路径经过节点本身向父节点发展
     *    3. 最大路径就是节点本身
     *  可以将左右边子树返回的满足情况2的最大路径和f(left),f(right)
     *  ，以及节点本身值val, 做一个组合，假设当前最大值是MAX
     *  MAX = max(val, f(left)+val+f(right), f(left)+val, f(right)+val)
     *  因为要满足递归条件，向上级返回的f(n)只能是情况2或者3
     *  f(n) = max(val, f(left)+val, f(right)+val)
     */
    int MAX = Integer.MIN_VALUE;
    public int calculate(TreeNode node){
        if(node == null) return 0;
        int left = 0;
        int right = 0;
        if(node.left!=null) left = calculate(node.left);
        if(node.right!=null) right = calculate(node.right);
        int sum = node.val;
        if(left>0) sum += left;
        if(right>0) sum += right;
        MAX = Math.max(MAX, sum);
        return Math.max(node.val, Math.max(left+node.val, right+node.val));
    }
    public int maxPathSum(TreeNode root) {
        calculate(root);
        return MAX;            
    }
}

public class Solution {

    int max = Integer.MIN_VALUE;

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


    // 每个节点返回最大值
    public int process(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftData = Math.max(0, process(root.left));
        int rightData = Math.max(0, process(root.right));
        int sum = leftData + rightData + root.val;
        max = Math.max(sum, max);
        return Math.max(leftData, rightData) + root.val;
    }
}

// 对于每个节点都要考虑：  【递归】
//    1\. 自己作为 root是不是就已经全局最大了（全局参数max，一直在更新）
//    2\. 这个节点的最大单边贡献（需要累加）
import java.lang.Integer;
public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root==null)    return 0;
        run(root);
        return max;
    }

    //1\. 是不是天选之点（更新max）  2.return:单边最大贡献
    public int run(TreeNode t){
        int leftContribution = 0;
        int rightContribution = 0;
        int currentMax = t.val; //负的也得经过自己这个节点

        if(t.left!=null)     leftContribution = run(t.left);
        if(t.right!=null)    rightContribution = run(t.right);

        //算自己作为root的最大值，看是不是天选之点
        if(leftContribution>0)     currentMax = currentMax + leftContribution;
        if(rightContribution>0)    currentMax = currentMax + rightContribution;
        if(currentMax > max){
            max = currentMax;
        }

        return Math.max(t.val, Math.max(t.val+leftContribution, t.val+rightContribution));
    }
}

class Solution {
    int maxDis;
public:
    int maxPathSum(TreeNode *root) {
        if(!root){
            maxDis=0;
            return -1e8;
        }
        int lMax=maxPathSum(root->left),l=max(0,maxDis);
        int rMax=maxPathSum(root->right),r=max(0,maxDis);
        maxDis=max(l,r)+root->val;
        return max(lMax,max(rMax,l+r+root->val));
    }
};

public class Solution {  
    private int max = Integer.MIN_VALUE;  
      
    public int maxPathSum(TreeNode root) {  
        maxSum(root);  
        return max;  
    }  
      
    public int maxSum(TreeNode root) {
		if(root == null) return 0;
		int leftVal = maxSum(root.left);
		int rightVal = maxSum(root.right);
		int curMax = root.val;
		if(leftVal > 0) curMax += leftVal;
		if(rightVal > 0) curMax += rightVal;
		max = max > curMax ? max : curMax;
		return Math.max(root.val, Math.max(root.val + leftVal, root.val + rightVal));
	}
}  

public class Solution {
    int maxValue;
    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPathDown(root);
        return maxValue;     
    }
    private int maxPathDown(TreeNode node){
        if(node==null)
            return 0;
        int left = Math.max(0, maxPathDown(node.left));
        int right = Math.max(0, maxPathDown(node.right));
        maxValue = Math.max(maxValue, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}

/*
 * 124. Binary Tree Maximum Path Sum
 * 解题思路：（转载自：http://blog.csdn.net/linhuanmars/article/details/22969069）
 * 这道题是求树的路径和的题目，不过和平常不同的是这里的路径不仅可以从根到某一个结点，
 * 而且路径可以从左子树某一个结点，然后到达右子树的结点，就像题目中所说的可以起始和终结于任何结点。
 * 在这里树没有被看成有向图，而是被当成无向图来寻找路径。
 * 因为这个路径的灵活性，我们需要对递归返回值进行一些调整，而不是通常的返回要求的结果。
 * 在这里，函数的返回值定义为以自己为根的一条从根到子结点的最长路径（这里路径就不是当成无向图了，
 * 必须往单方向走）。
 * 这个返回值是为了提供给它的父结点计算自身的最长路径用，
 * 而结点自身的最长路径（也就是可以从左到右那种）则只需计算然后更新即可。
 * 这样一来，一个结点自身的最长路径就是它的左子树返回值（如果大于0的话），
 * 加上右子树的返回值（如果大于0的话），再加上自己的值。
 * 而返回值则是自己的值加上左子树返回值，
 * 右子树返回值或者0（注意这里是“或者”，而不是“加上”，因为返回值只取一支的路径和）。
 * 在过程中求得当前最长路径时比较一下是不是目前最长的，如果是则更新。
 * 算法的本质还是一次树的遍历，所以复杂度是O(n)。而空间上仍然是栈大小O(logn)。
 */

// 因为maxPathSum不一定经过根节点，所以用maxValue整个遍历过程中出现过的最大值
	int maxValue = 0;

	public int maxPathSum(TreeNode root) {
		if (root == null)
			return 0;
		maxValue = Integer.MIN_VALUE;
		getMaxPathSum(root);
		return maxValue;
	}

	private int getMaxPathSum(TreeNode root) {
		if (root == null)
			return 0;
		//因为节点的值可以为负数，所以最大值取0和子树值的较大者
		int leftMax = Math.max(0, getMaxPathSum(root.left));
		int rightMax = Math.max(0, getMaxPathSum(root.right));
		//如果将当前root作为根节点，那么最大值是root.val+左子树最大值+右子树最大值
		maxValue = Math.max(maxValue, root.val + leftMax + rightMax);
		//只能返回左右子树中较大值加上root.val
		return Math.max(0, root.val + Math.max(leftMax, rightMax));
	}

class Solution {
public:     int Max;
    int maxPathSum(TreeNode *root) {
        Max = INT_MIN;
        maxSum(root);         return Max;
    }
    int maxSum(TreeNode *root){
        if(root == NULL)
            return 0;
        int l_Max = max(0, maxSum(root->left));
        int r_Max = max(0, maxSum(root->right));
        Max = max(Max, l_Max + r_Max + root->val);
        return max(l_Max, r_Max) + root->val;     }
};

class Solution:
    def __init__(self):
        self.max_weight = -10000

    def maxPathSum(self, root: TreeNode) -> int:
        # write code here
        self.maxPath(root)
        return self.max_weight

    def maxPath(self, root):
        if root is None:
            return 0
        left_weight = self.maxPath(root.left)
        right_weight = self.maxPath(root.right)
        self.max_weight = max(
            self.max_weight,
            root.val + left_weight + right_weight,
            root.val,
            root.val + left_weight,
            root.val + right_weight,
        )
        ret = max(root.val, root.val + left_weight, root.val + right_weight)
        return ret