LeetCode题目之腾讯精选练习（50题）：二叉树中的最大路径和

心已赠人 2024-04-18 22:20 25阅读 0赞

# 题目 #

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

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

**示例 1** :

输入: [1,2,3]
    
           1
          / \
         2   3
    
    输出: 6

**示例 2** :

输入: [-10,9,20,null,null,15,7]
    
       -10
       / \
      9  20
        /  \
       15   7
    
    输出: 42

## 算法实现 ##

int max_sum = int.MinValue;
    public int max_gain(TreeNode node)
    {
        
        if (node == null) return 0;
    
        // max sum on the left and right sub-trees of node
        int left_gain = Math.Max(max_gain(node.left), 0);
        int right_gain = Math.Max(max_gain(node.right), 0);
    
        // the price to start a new path where `node` is a highest node
        int price_newpath = node.val + left_gain + right_gain;
    
        // update max_sum if it's better to start a new path
        max_sum = Math.Max(max_sum, price_newpath);
    
        // for recursion :
        // return the max gain if continue the same path
        return node.val + Math.Max(left_gain, right_gain);
    }
    
    public int MaxPathSum(TreeNode root)
    {
        
        max_gain(root);
        return max_sum;
    }

## 执行结果 ##

**执行结果** : 通过  
**执行用时** : 144 ms, 在所有 C\# 提交中击败了100.00%的用户  
**内存消耗** : 29.4 MB, 在所有 C\# 提交中击败了62.50%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

## 小的总结 ##

本次题对我来说很难，可以说完全没有思路。在看过官网题解后，看懂并理解了它的算法，很精妙，看来自己对二叉树的理解还不是很深。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/cb0be03558344f26967d4a3a5368e761.png