LeetCode | Binary Tree Maximum Path Sum

发布时间:2017-2-26 6:56:55 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode | Binary Tree Maximum Path Sum",主要涉及到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, 1 / \ 2 3 Return 6. 分析 通过不断递归左右子树进行求解,需要求出左右子树的Maximum Path Sum,同时,为了求出当前节点的Maximum Path Sum,还需要记录子树中包含子树根节点(能与当前节点联通)的并且拥有Maximum Sum的“树枝”。 代码 public class BinaryTreeMaximumPathSum { public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } class Result { int maxPathSum; int maxSingleBranchSum; } private Result solve(TreeNode root) { Result result = new Result(); if (root.left == null && root.right == null) { result.maxPathSum = root.val; result.maxSingleBranchSum = root.val; return result; } // get max path sum & max single branch sum int maxPathSum = root.val; int maxSingleBranchSum = root.val; Result leftResult = null; Result rightResult = null; if (root.left != null) { leftResult = solve(root.left); if (leftResult.maxSingleBranchSum > 0) { maxPathSum += leftResult.maxSingleBranchSum; maxSingleBranchSum += leftResult.maxSingleBranchSum; } } if (root.right != null) { rightResult = solve(root.right); if (rightResult.maxSingleBranchSum > 0) { maxPathSum += rightResult.maxSingleBranchSum; maxSingleBranchSum = Math.max(maxSingleBranchSum, root.val + rightResult.maxSingleBranchSum); } } if (leftResult != null) { maxPathSum = Math.max(maxPathSum, leftResult.maxPathSum); } if (rightResult != null) { maxPathSum = Math.max(maxPathSum, rightResult.maxPathSum); } result.maxPathSum = maxPathSum; result.maxSingleBranchSum = maxSingleBranchSum; return result; } public int maxPathSum(TreeNode root) { if (root == null) { return Integer.MIN_VALUE; } return solve(root).maxPathSum; } }

上一篇:gdb初识
下一篇:re映射

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。