首页 > 代码库 > Leetcode-Bianry Tree Maximum Path Sum
Leetcode-Bianry 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.
Solution:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ //NOTE: Need to consider about negtive number, or ask interviewer about this issue! //NOTE2: at every node, we need consider about three cases. //1. the path start from some node in the lower level and end at the current node, called singlePath. //2. the path from some child node in the left and end at some child node at right, called combinePath. //3. the path that does not contain the current node, called lowPath. //curNode: //singlePath = max(left.singlePath, right.singlePath, curNode.val); //combinePath = curNode.val+left.singlePath+right.singlePath; //lowPath = max(left.combinePath, left.singlePath, left.lowPath, right.ALLPATH); //Return: //max(root.singlePath, root.combinePath, root.lowPath);class PathInfo{ public int singlePath; public int combinePath; public int lowPath; public int singleNodePath; public PathInfo(){ singlePath = 0; combinePath = 0; lowPath = 0; }} public class Solution { public int maxPathSum(TreeNode root) { PathInfo rootInfo = new PathInfo(); rootInfo = maxPathSumRecur(root); int max = rootInfo.singlePath; if (rootInfo.combinePath>max) max = rootInfo.combinePath; if (rootInfo.lowPath>max) max = rootInfo.lowPath; return max; } public PathInfo maxPathSumRecur(TreeNode curNode){ //If current node is a leaf node if (curNode.left==null&&curNode.right==null){ PathInfo path = new PathInfo(); path.singlePath = curNode.val; path.combinePath = curNode.val; path.lowPath = curNode.val; return path; } //If not, then get the PathInfo of its child nodes. PathInfo left = null; PathInfo right = null; PathInfo cur = new PathInfo(); if (curNode.left!=null) left = maxPathSumRecur(curNode.left); if (curNode.right!=null) right = maxPathSumRecur(curNode.right); //Now calculate the PathInfo of current node. if (right==null) cur.singlePath = curNode.val+left.singlePath; else if (left==null) cur.singlePath = curNode.val+right.singlePath; else { if (left.singlePath>right.singlePath) cur.singlePath = curNode.val+left.singlePath; else cur.singlePath = curNode.val+right.singlePath; } if (cur.singlePath<curNode.val) cur.singlePath=curNode.val; if (right==null) cur.combinePath = curNode.val+left.singlePath; else if (left==null) cur.combinePath = curNode.val+right.singlePath; else cur.combinePath = curNode.val+left.singlePath+right.singlePath; int max = Integer.MIN_VALUE; if (right==null){ max = left.lowPath; if (left.combinePath>max) max = left.combinePath; } else if (left==null){ max = right.lowPath; if (right.combinePath>max) max = right.combinePath; } else { max = left.lowPath; if (left.combinePath>max) max = left.combinePath; if (right.lowPath>max) max = right.lowPath; if (right.combinePath>max) max = right.combinePath; } if (max<cur.singlePath) max=cur.singlePath; cur.lowPath = max; return cur; }}
递归求解：对于当前node，计算三种情况的max path sum.
Leetcode-Bianry Tree Maximum Path Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。