首页 > 代码库 > [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,
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;>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。