一天一大 leet(二叉树中的最大路径和)难度:困难 DAY-21

前端小书童

发布于 2020-09-24 11:23:51

2710

发布于 2020-09-24 11:23:51

文章被收录于专栏：前端小书童

题目(难度:困难):

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例

示例 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);
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-06-21，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树