二叉树的最大路径和
给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。
这个路径的开始节点和结束节点可以是二叉树中的任意节点
/*
* function TreeNode(x) {
* this.val = x;
* this.left = null;
* this.right = null;
* }
*/
/**
*
* @param root TreeNode类
* @return int整型
*/
function maxPathSum( root ) {
// write code here
var maxSum = -Infinity
function getMax(root){
if(!root) return 0;
let leftSum = Math.max(0,getMax(root.left))
let rightSum = Math.max(0,getMax(root.right))
maxSum = Math.max(maxSum,leftSum + rightSum + root.val)
// dfs找最大值
return Math.max(0,Math.max(leftSum,rightSum)+root.val)
}
getMax(root)
return maxSum
}
module.exports = {
maxPathSum : maxPathSum
};树算法 文章被收录于专栏
树相关算法
360集团公司福利 388人发布
投递萤石等公司10个岗位
查看1道真题和解析