精选50题之 124. 二叉树中的最大路径和

迷南。 2024-04-20 10:19 2阅读 0赞

### 腾讯精选练习（50 题）之 124. 二叉树中的最大路径和 ###

*   *  原题目链接
     *  题目分析
     *  解题分析
     *  代码实现
     *  其他方式
     *  写在最后

## [原题目链接][Link 1] ##

给定一个非空二叉树，返回其最大路径和。  
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]

## 题目分析 ##

涉及到搜索以及不同层结点值的比较，且父亲节点对应的值等于其左孩子和右孩子的数值的代数和。应该使用的是递归的思想。

## 解题分析 ##

首先，需要定义一个递归函数pathsum。  
要注意的是：由于递归中涉及比较，并非递归到叶节点再回到根节点，返回数值就是最终解，这就需要另一个变量储存最大数值。然而一个函数中只能有一个返回值，随意暂存变量需要使用隐含传值（函数中加入一个形参也可以）。所以

*  节点深度为 0 时，返回值定义为 0，暂存变量记录“根”节点数值（每次递归，新的父亲节点都被称为根节点）
 *  节点深度不为 0 时，即左、右孩子结点至少有一个不为空，递归遍历。而且根据性质，如果一个父节点的左、右孩子节点路径和 <=0 时，需要舍弃（负增益）。
 *  递归返回

PS. 三元运算符相较max()，min() 更节省时间和空间，已改写代码。但如下代码会使得在巨量数据集下运行超时。

> int left = pathsum(root->left, max\_path) > 0 ? pathsum(root->left, max\_path) : 0;

是递归过程中函数返回值的问题？

## 代码实现 ##

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
        
    public:
        int maxPathSum(TreeNode* root) 
        {
        
            int max_path = INT_MIN;
            pathsum(root, max_path);
            return max_path;
        }
        int pathsum(TreeNode* root, int& max_path) 
        {
        
            if (root == NULL) 
                return 0;
            int left = max(pathsum(root->left, max_path), 0);//左递归
            int right = max(pathsum(root->right, max_path), 0);//右递归
            max_path = max_path > left + right + root->val ? max_path : left + right + root->val;
            return left > right ? left + root->val: right + root->val;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 2]  
复杂度分析：

*  时间复杂度：O(N)
 *  空间复杂度：O(1)

## 其他方式 ##

动态规划? 还有这等操作？？？

[0x404 的回答][0x404]

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
        
    public:
        map<TreeNode*,int> maxSum;
        map<TreeNode*,int> upSum;
        int ans = -2147483648;
        void dp_up(TreeNode* r){
        
            maxSum[r] = r->val;
            if(r->left == NULL && r->right == NULL){
        
                return;
            }
            if(r->left) dp_up(r->left);
            if(r->right) dp_up(r->right);
            int tmp = max(maxSum[r->left],maxSum[r->right]);
            maxSum[r] = max(maxSum[r],maxSum[r]+tmp);
        }
        void dp_down(TreeNode* r){
        
            if(r->left == NULL && r->right == NULL){
        
                return;
            }
            if(r->left){
        
                int tmp = max(r->val + (r->right == NULL ? 0 : maxSum[r->right]),
                                     r->val + upSum[r]) ;
                upSum[r->left] = max(upSum[r->left],upSum[r->left] + tmp);
                dp_down(r->left);  
            }
            if(r->right){
        
                int tmp = max(r->val + (r->left == NULL ? 0 : maxSum[r->left]),
                                      r->val + upSum[r]);
                upSum[r->right] = max(upSum[r->right],upSum[r->right] + tmp);
                dp_down(r->right);
            }
        }
        void dfs(TreeNode* r){
        
            if(r->left == NULL && r->right == NULL){
        
                ans = max(ans,maxSum[r]+upSum[r]);
                //ans = max(ans,r->val+upSum[r]);
                return;
            }
            ans = max(ans,maxSum[r]+upSum[r]);
            //ans = max(ans,r->val+upSum[r]);
            if(r->left) dfs(r->left);
            if(r->right) dfs(r->right);
        }
        int maxPathSum(TreeNode* root) {
        
            dp_up(root);
            dp_down(root);
            dfs(root);
            return ans;
        }
    };

## 写在最后 ##

晚安。

[Link 1]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8d535ae4a2c944b2aaa48954b08855e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d21e0c8628704782a1056a3a6443e1e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/fe8d1aae65d14527af46b5b779b01cc3.png
[0x404]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/ni-mei-jian-guo-de-quan-xin-jie-fa-shu-shang-dp-by/