给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
输入: [1,2,3]
1
/ \
2 3
输出: 6
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
使用递归出来二叉树
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxPathSum = function(root) {
let _result = -Number.MAX_VALUE;
sum_node(root)
function sum_node(node) {
if (node === null) return 0;
let left = Math.max(sum_node(node.left), 0);
let right = Math.max(sum_node(node.right), 0);
_result = Math.max(_result, left + right + node.val);
return node.val + Math.max(left, right);
}
return _result
};
得到节点左侧右侧和的逻辑是一样 只是记录值的形式不同, 把当前节点能得到的最大和的值推送到数组中,再从数组中捡出最大值
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxPathSum = function(root) {
let resultArr = [];
let helper = function(node){
if(node == null) return 0;
let leftPathVal = Math.max(helper(node.left), 0);
let rightPathVal = Math.max(helper(node.right), 0);
resultArr.push(leftPathVal+rightPathVal+node.val)
return Math.max(leftPathVal,rightPathVal)+node.val;
}
resultArr.push(helper(root));
return Math.max.apply(null,resultArr);
};