94.Binary Tree Maximum Path Sum-二叉树中的最大路径和（中等题）

本文主要是介绍94.Binary Tree Maximum Path Sum-二叉树中的最大路径和（中等题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树中的最大路径和

题目

给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）
样例

给出一棵二叉树：

返回 6
题解

1.递归法
对于所有结点，如果路径把这个节点作为“最高点”，记录最长路径maxValue 。然后在递归中求出最大值即可。以根节点为例，对于经过根节点的最大路径的计算方式为：
找出左子树中以左子节点为起点的最大路径长度leftV ，和右子树中以右子节点为起点的最大路径长度rightV。然后这个点的maxValue为leftV +rightV+root.val, leftV +root.val, rightV+root.val, root.val中的最大值。需注意函数返回值表示的最大路径的起点必须是root节点。

/*** Definition of TreeNode:* public class TreeNode {*     public int val;*     public TreeNode left, right;*     public TreeNode(int val) {*         this.val = val;*         this.left = this.right = null;*     }* }*/
public class Solution {/*** @param root: The root of binary tree.* @return: An integer.*/private int maxValue = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {getMax(root);return maxValue;}private int getMax(TreeNode root){if (root == null){return 0;}int leftV = getMax(root.left);int rightV = getMax(root.right);maxValue = Math.max(maxValue,root.val+leftV+rightV);maxValue = Math.max(maxValue,root.val+leftV);maxValue = Math.max(maxValue,root.val+rightV);maxValue = Math.max(maxValue,root.val);int maxViaThisNode = Math.max(leftV + root.val, root.val);return Math.max(rightV + root.val,maxViaThisNode);}
}

2.分治法
LeetCode: Binary Tree Maximum Path Sum 解题报告

/*** Definition for binary tree* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class Solution {public class ReturnType {int maxSingle;int max;ReturnType (int maxSingle, int max) {this.max = max;this.maxSingle = maxSingle;}}public int maxPathSum(TreeNode root) {return dfs(root).max;        }public ReturnType dfs(TreeNode root) {ReturnType ret = new ReturnType(Integer.MIN_VALUE, Integer.MIN_VALUE);if (root == null) {return ret;}ReturnType left = dfs(root.left);ReturnType right = dfs(root.right);int cross = root.val;// if any of the path of left and right is below 0, don't add it.cross += Math.max(0, left.maxSingle);cross += Math.max(0, right.maxSingle);// 注意，这里不可以把Math.max(left.maxSingle, right.maxSingle) 与root.val加起来，// 会有可能越界！int maxSingle = Math.max(left.maxSingle, right.maxSingle);// may left.maxSingle and right.maxSingle are below 0maxSingle = Math.max(maxSingle, 0);maxSingle += root.val;ret.maxSingle = maxSingle;ret.max = Math.max(right.max, left.max);ret.max = Math.max(ret.max, cross);return ret;}
}