124. 二叉树中的最大路径和 - Binary Tree Maximum Path Sum
【后序遍历】 【动态规划】
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
Example:
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
Solutions
1
2
3
4
5
6
7
8
9
|
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
|
Solution 【后序遍历】 【动态规划】 ( 3ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
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;
}
}
}
|
Notes