[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.

Example 1:

Input: [1,2,3] 1 / \ 2 3 Output: 6

Example 2:

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

 

题意：

从二叉树任意节点出发，到任意节点终止。计算最大路径和。

 

思路：

路径从任意节点出发，到任意节点终止。

所有满足条件的path中和最大的一条path

Max (以任意一个点为顶点的所有path中和最大是多少)

以任意一个点为顶点的path  

(1) left_max (左边直上直下的path)

(2)right_max(右边直上直下的path)

(3)当前点自己

 

 

(1)left_max +  (2)right_max +(3)当前点自己

 

代码：

1 class Solution { 2 public int maxPathSum(TreeNode root) { 3 // corner case 4 if(root == null){return 0;} 5 int[] maxPath = new int[]{Integer.MIN_VALUE}; 6 dfs(root, maxPath); 7 return maxPath[0]; 8 } 9 10 private int dfs(TreeNode root, int[]maxPath){ 11 int left = root.left != null ? Math.max(dfs(root.left, maxPath), 0) : 0; 12 int right = root.right != null ? Math.max(dfs(root.right, maxPath), 0) : 0; 13 int cur = root.val + left + right; 14 maxPath[0] = Math.max(maxPath[0], cur); 15 return root.val + Math.max(left, right); 16 } 17 }

 

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