関小君刷题记

二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=124

解题思路分析：

对于二叉树中任意一个节点，他能组成的最大路径和有4种可能：

1. 当前节点值加上左子树的最大路径和
2. 当前节点值加上右子树的最大路径和
3. 当前节点值自身
4. 当前节点值加上左子树的最大路径和，再加上右子树的最大路径和

解题时，我们使用dfs递归的方式遍历二叉树中的所有节点，对于当前节点，我们利用上述4钟情况中的最大值去更新全局最大值。另外，需要注意一下递归函数的返回值，上述情况的前三种中的最大值可以最为返回值返回给上层递归。由于第四种情况与当前节点的父节点无法组成一条合理路径，因此最后一种情况不能作为返回值返回。

其实本题与 LEETCODE 1245. Tree Diameter 解题思路分析 的思路非常相似，那一题求的是最长路径，而本题求的是最大路径和。

实现代码：

int max=Integer.MIN_VALUE; // 最大值，返回结果
public int maxPathSum(TreeNode root) {
    help(root); // dfs递归
    return max;
}

int help(TreeNode root){
    if(root==null) return 0; // 当前节点为空，返回0
    int sumLeft=help(root.left); // 左子树的最大路径和
    int sumRight=help(root.right); // 右子树的最大路径和
    // 求出当前节点值加上左子树最大路径和，当前节点值加上右子树最大路径和
    // 以及当前节点值本身，这三者中的最大值，作为当前递归返回值
    int res=Math.max(root.val,Math.max(root.val+sumLeft,root.val+sumRight));
    // 比较当前递归返回值与左右子树的最大路径和加上当前节点组成的路径和
    // 更新全局最大值
    max=Math.max(max, Math.max(root.val+sumLeft+sumRight,res));
    return res;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Maximum Path Sum.

Memory Usage: 41.2 MB, less than 22.62% of Java online submissions for Binary Tree Maximum Path Sum.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-124-binary-tree-maximum-path-sum-解题思路分析/