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

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

题目

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;>