一天一大 leet(二叉树中的最大路径和)难度:困难 DAY-21
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例
- 示例 1
输入: [1,2,3]
1
/ \
2 3
输出: 6- 示例 2
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42抛砖引玉
使用递归出来二叉树
- 任取树中的一个节点，有两个选择，向左累计求和或者向右累计求和
- 借用递归，假设已经知道左侧的和右侧的和,sum(node.left),sum(node.right)
- 那如果结果路径中包含这个节点，和的组成是：
/**
* 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);
};举报
腾讯云开发者
