[leetcode]124. Binary Tree Maximum Path Sum二叉树最大路径和

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Input: [1,2,3] 1 / \ 2 3 Output: 6 Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 Output: 42

 

题意：

在BST中找到一条path（这条path至少包含一个node）使它path上所有node的和最大

 

思路：

这是一道关于BST和recursion的经典题，需要掌握

最naive的想法是找到所有BST的path，返回max

发现， 任意一条path都有一个顶点（位置最高点）

我们用这个顶点来分解所有path

这样，以任意一个点为顶点的path就分解为

a. max_sum (左边path)

b. max_sum (右边path)

c. 顶点自己的value

进一步，

a + b + c 组成的人字形path的max path sum

2 / \ 1 -3

dfs的return value :  2(顶点自己的value必须加上，无论正负) +  1 （正数贡献自己） + 0 (-3为负数不做贡献就是及时止损了)  = 3 

 

代码：

1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 class Solution { 11 public int maxPathSum(TreeNode root) { 12 // corner case 13 if(root == null){ 14 return 0; 15 } 16 int[] maxPath = new int[]{Integer.MIN_VALUE}; 17 dfs(root, maxPath); 18 return maxPath[0]; 19 } 20 21 private int dfs(TreeNode root, int[]maxPath){ 22 int left = root.left != null ? Math.max(dfs(root.left, maxPath), 0) : 0; 23 int right = root.right != null ? Math.max(dfs(root.right, maxPath), 0) : 0; 24 int cur = root.val + left + right; 25 maxPath[0] = Math.max(maxPath[0], cur); 26 return root.val + Math.max(left, right); 27 } 28 }

 

 

 

转载于:https://www.cnblogs.com/liuliu5151/p/9070198.html

相关资源：数据结构—成绩单生成器