二叉树中的最大路径和
题目：
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1：
1
/
2 3
输出：6
示例 2：
-10
/
9 20
/
15 7
输出：42
思路
路径每到一个节点，我们有三种选择，
1.停留在节点
2.走向左子节点
3.走向右子节点
走到下一个节点后，我们又要面临这样的选择。
故可以使用递归的思路
（注意 不能既走左子节点又走右子节点，这样将会导致路径重复）
我们只需关心从子树中获取最大收益，而无需关心具体的实现路径，这就是一种递归、自顶向下的思考。
我们定义深度优先搜索DFS函数，用于求出子树中的最大路径和。
还是分为三种情况：
1.停留在当前节点 收益： node.val
2.走入左子树 收益： node.val +leftPathSum
3.走入右子树 收益： node.val +rightPathSum
如果左右子树收益为负，我们则舍弃之。即：
leftPathSum = Math.max(DFS(node.left), 0);
rightPathSum = Math.max(DFS(node.right), 0);
题目还说不一定经过根节点，说明最大路径和可能存在局部子树中，则我们需要在每一次递归时求一下当前的最大路径和。
如果能够明白上述思路，就可以清楚明白我们的代码。
class Solution {
int maxSum = Integer.MIN_VALUE; // 记录最大路径和
public int maxPathSum(TreeNode root) {
DFS(root);
return maxSum;
}
public int DFS(TreeNode node) {
if (node == null)
return 0;
int leftPathSum = Math.max(DFS(node.left), 0);
int rightPathSum = Math.max(DFS(node.right), 0);
// 每次递归时求最大路径和
maxSum = Math.max(maxSum, node.val + leftPathSum + rightPathSum);
// 返回子树的最大路径和
return node.val + Math.max(leftPathSum, rightPathSum);
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
