题解 | #二叉树中的最大路径和#
二叉树中的最大路径和
http://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a
dfs深度优先搜索，对于每一个节点，有两种角色：
1、作为根节点，计算构建的树的最大路径和，此时需要left+right+rootVal,因为可以只取一部分，所以要判断左右的值是否小于0，负数的话就是舍弃。但是root本身是不是负数不需要关心，因为对于一棵树而言，最大路径和无非就是root，left，right，root+left，root+right，root+left+right,left和right在下一次自己作为根节点的时候会去和res比较取最大值的，而rootVal+left+right>=rootVal,不管rootVal是什么值，都保留了较大的那个值。
2、作为子树，返回的时候根据题目意思，就只能取rootVal+Math.max(left,right);
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型
*/
public int res=Integer.MIN_VALUE;
public int maxPathSum (TreeNode root) {
dfs(root);
return res;
}
int dfs(TreeNode root){
if(root==null){
return 0;
}
//作为根树计算的时候
int rootVal=root.val;
int left=Math.max(dfs(root.left),0);
int right=Math.max(dfs(root.right),0);
res=Math.max(res,rootVal+left+right);
return rootVal+Math.max(left,right); //作为子树返回的时候
}
}
查看26道真题和解析
