首页 > 代码库 > [LeetCode]Binary Tree Maximum Path Sum, 解题报告

[LeetCode]Binary Tree Maximum Path Sum, 解题报告

2024-07-04 00:44:20   227人阅读

题目

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,


Return 6.

思路

考虑当二叉树中所有节点均为正数时，一颗二叉树的最大路径，就是其左子树的最大路径和 + 当前节点值 + 右子树最大路径的和。可以考虑从根节点出发通过深度优先搜索来求解：

（1） 如果是叶子节点，则返回叶子节点的值

（2）如果不是叶子节点，
  • 左子树路径和 = 递归查找左子树
  • 右子树路径和 = 递归查找右子树
  • 如果 左子树路径和 + 右子树路径和 + 当前节点值 > 当前最大路径和，则更新当前最大路径和
（3）返回MAX {当前节点 + 左子树路径和， 当前节点 + 右子树路径和}

我想这里大家可能有两处疑问：

（1）二叉树节点中存在负数怎么办？

（2）为什么返回的MAX {当前节点 + 左子树路径和， 当前节点 + 右子树路径和}，而不是返回（当前节点+左子树路径和 + 右子树路径和）？

下面我分别解释这两个问题：

（1）二叉树节点中存在负数怎么办？

这里解决方法比较简单，以左子树路径和为例，得到左子树路径和具体值后和0做比较，< 0 则返回0, >0则返回具体值

（2）为什么返回的MAX {当前节点 + 左子树路径和， 当前节点 + 右子树路径和}，而不是返回{ 当前节点+左子树路径和 + 右子树路径和 }？

因为这里路径不能存在重复节点，二叉树路径的定义是每个节点只能访问一次，如果返回的是{ 当前节点+左子树路径和 + 右子树路径和 }，则必然存在某一相对根节点多次访问的情况，示例二叉树结构如下：

以节点2为例，返回到根节点1的值应该为2+5=7,而不是2+4+5=11,因为2只能访问一次


AC代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private static int maxValue;
    
    public static int maxPathSum(TreeNode root) {
        maxValue = http://www.mamicode.com/root == null ? 0 : root.val;>


联系
我们