（js）leetcode 124. 二叉树中的最大路径和

红太狼 2023-01-08 04:23 188阅读 0赞

### 题目： ###

> 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径 至少包含一个 节点，且不一定经过根节点。
> 
> 路径和 是路径中各节点值的总和。
> 
> 给你一个二叉树的根节点 root ，返回其 最大路径和 。
> 
> 示例 1：
> 
> ![ca0d0d9f728f2aeda1976de9b08940e5.png][]  
> 输入：root = \[1,2,3\]  
> 输出：6  
> 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6  
> 示例 2：
> 
> ![730fd58fb57c0fbc6d5f77b18e9d6b50.png][]  
> 输入：root = \[-10,9,20,null,null,15,7\]  
> 输出：42  
> 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

### 思路： ###

> 1. 每递归一个子树，都求当前子树内部的最大路径和，然后比较出最大的。
> 
> 2. 一个子树内部的最大路径和 = 左子树提供的最大路径和 + 根节点值 + 右子树提供的最大路径和
> 
> 思路参考：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/shou-hui-tu-jie-hen-you-ya-de-yi-dao-dfsti-by-hyj8/

### 代码实现： ###

/**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    
    var maxPathSum = function(root) {
        let ans = Number.MIN_SAFE_INTEGER;
        var oneSideMax = function(root) {
            if(root === null) return 0;
            let left = Math.max(0, oneSideMax(root.left));
            let right = Math.max(0, oneSideMax(root.right));
            ans = Math.max(ans, left + right + root.val);
            return Math.max(left, right) + root.val;
        };
    
        oneSideMax(root);
        return ans;
    };

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70][]

[ca0d0d9f728f2aeda1976de9b08940e5.png]: /images/20221119/9df46ae6811e45318188e35d42c8c9ec.png
[730fd58fb57c0fbc6d5f77b18e9d6b50.png]: /images/20221119/57305f155da6422db7e87390869686f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70]: /images/20221119/70a57f5c353a45cd870e43fc931491aa.png