首页 > 代码库 > 124. Binary Tree Maximum Path Sum
124. Binary Tree Maximum Path Sum
感觉和53.maximum subarray有相似处，维护一个localMax,一个globalMax
localMax是指左右只选一条的max，简单表示是Math.max(left, right) + nums[i].其实left和right的值因为可能是负数，所以left/right的值是0或者选
globalMax是指以当前节点为中心节点两侧总和最大，简单说是Math.max(local, global);
最后返回左右中比较大的一条供上一级节点来选择。
1 int global = Integer.MIN_VALUE; 2 3 public int maxPathSum(TreeNode root) { 4 helper(root); 5 return global; 6 } 7 8 private int helper(TreeNode root) { 9 if(root == null) {10 return 0;11 }12 int left = Math.max(0, helper(root.left));13 int right = Math.max(0, helper(root.right));14 global = Math.max(global, left + right + root.val);15 return Math.max(left, right) + root.val;16 }
是dfs, time complexity应该是O(n)
124. Binary Tree Maximum Path Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。