首页 > 代码库 > LeetCode: Binary Tree Maximum Path Sum 解题报告
LeetCode: Binary Tree Maximum Path Sum 解题报告
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,
1
/ \
2 3
SOLUTION 1:
计算树的最长path有2种情况：
1. 通过根的path.
(1)如果左子树从左树根到任何一个Node的path大于零，可以链到root上
(2)如果右子树从右树根到任何一个Node的path大于零，可以链到root上
2. 不通过根的path. 这个可以取左子树及右子树的path的最大值。
所以创建一个inner class:
记录2个值：
1. 本树的最大path。
2. 本树从根节点出发到任何一个节点的最大path.
注意，当root == null,以上2个值都要置为Integer_MIN_VALUE; 因为没有节点可取的时候，是不存在solution的。以免干扰递归的计算
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public class ReturnType {12 int maxSingle;13 int max;14 ReturnType (int maxSingle, int max) {15 this.max = max;16 this.maxSingle = maxSingle;17 }18 }19 20 public int maxPathSum(TreeNode root) {21 return dfs(root).max; 22 }23 24 public ReturnType dfs(TreeNode root) {25 ReturnType ret = new ReturnType(Integer.MIN_VALUE, Integer.MIN_VALUE);26 if (root == null) {27 return ret;28 }29 30 ReturnType left = dfs(root.left);31 ReturnType right = dfs(root.right);32 33 int cross = root.val;34 35 // if any of the path of left and right is below 0, don‘t add it.36 cross += Math.max(0, left.maxSingle);37 cross += Math.max(0, right.maxSingle);38 39 // 注意，这里不可以把Math.max(left.maxSingle, right.maxSingle) 与root.val加起来，40 // 会有可能越界！41 int maxSingle = Math.max(left.maxSingle, right.maxSingle);42 43 // may left.maxSingle and right.maxSingle are below 044 maxSingle = Math.max(maxSingle, 0);45 maxSingle += root.val;46 47 ret.maxSingle = maxSingle;48 ret.max = Math.max(right.max, left.max);49 ret.max = Math.max(ret.max, cross);50 51 return ret;52 }53 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/tree/MaxPathSum.java
LeetCode: Binary Tree Maximum Path Sum 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。