You've successfully subscribed to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# 124. 二叉树中的最大路径和 - Binary Tree Maximum Path Sum

## 124. 二叉树中的最大路径和 - Binary Tree Maximum Path Sum

【后序遍历】 【动态规划】

给定一个非空二叉树，返回其最大路径和。



### Example:

输入: [1,2,3]

1
/ \
2   3



输入: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7



## Solutions

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/


### Solution 【后序遍历】 【动态规划】 ( 3ms)

class Solution {
private int result = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
getMax(root);
return result;
}

/* postOrderTranversal */
private int getMax(TreeNode r) {
if(r == null) return 0;
/* 并不是两个叶节点的距离 */
/* 如果子树路径和为负则应当置0表示最大路径不包含子树 */
int left = Math.max(0, getMax(r.left));
int right = Math.max(0, getMax(r.right));
/* 判断在该节点包含左右子树的路径和是否大于当前最大路径和*/
result = Math.max(result, r.val + left + right);
return Math.max(left, right) + r.val;
}
}


### Solution  ( 1ms)

class Solution {

int ans;

public int maxPathSum(TreeNode root) {
ans = Integer.MIN_VALUE;
maxDeep(root);
return ans;
}

public int maxDeep(TreeNode root) {
if (root == null) return 0;
//叶子结点
if (root.left == null && root.right == null) {
ans = Math.max(ans, root.val);
return root.val;
} else {
int left = maxDeep(root.left);
int right = maxDeep(root.right);
int tmp = Math.max(left, right )+ root.val; //当前节点到其子节点的最长路径
tmp = Math.max(tmp, root.val); //是否可以不经过其子节点
ans = Math.max(ans, tmp);
ans = Math.max(ans, left+right+root.val);
return tmp;
}
}

}