[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 = root == null ? 0 : root.val; findPath(root); return maxValue; } public static int findPath(TreeNode root) { if (root == null) { return 0; } int left = Math.max(findPath(root.left), 0); int right = Math.max(findPath(root.right), 0); maxValue = Math.max(maxValue, root.val + left + right); int current = Math.max(root.val, Math.max(root.val + left, root.val + right)); return current; } }