leetcode/code/lc124.java at master · mJackie/leetcode · GitHub

31 lines (31 loc) · 1.16 KB

package code;

* 124. Binary Tree Maximum Path Sum

* 题意：二叉树中找和最大的路径

* 难度：Hard

* 分类：Tree, Depth-first Search

* 思路：因为二叉树只有两个节点，一条路径可以想象成倒V字，从低层的某个节点一路向上，到达一个顶点，再一路向下，理解了这一点，整道题就好解了。

* Tips：用了一个全局变量存储最后结果，因为函数返回的是直线路径上的最优解，而不是V字路径最优解

* lc112, lc113, lc437, lc129, lc124, lc337, lc543, lc1026

public class lc124 {

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val = x; }

}

int res = Integer.MIN_VALUE; //可能小于0

public int maxPathSum(TreeNode root) {

dfs(root);

return res;

}

public int dfs(TreeNode root){

if(root==null)

return 0;

int left = Math.max(dfs(root.left),0);

int right = Math.max(dfs(root.right),0);

res = Math.max(res, left+right+root.val); //该节点是路径上的最高层节点

return Math.max(left,right)+root.val;

}

Expand file tree