【Leetcode】124. Binary Tree Maximum Path Sum（二叉树最大路径）

女爷i 2022-02-13 03:53 182阅读 0赞

Given a **non-empty** binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain **at least one node** and does not need to go through the root.

**Example 1:**

Input: [1,2,3]
    
           1
          / \
         2   3
    
    Output: 6

**Example 2:**

Input: [-10,9,20,null,null,15,7]
    
       -10
       / \
      9  20
        /  \
       15   7
    
    Output: 42

题目大意：

我们需要计算出二叉树当中取值最大的一个路径，题目当中如此描述树中的路径，该路径一定通过父节点同时到左右两个子树的节点只能有一个。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjAwMTM3_size_16_color_FFFFFF_t_70][]

解题思路：

找出当前节点左右两个侧的最大值，作为父节点的传入值。同时如果满足了有（左中右）存在最大值，则比较当前的最大值。

class Solution {
    private:
        int ans;
        int helper(TreeNode *tmp){
            
            if(tmp->left==NULL&&tmp->right==NULL){
                return tmp->val;
            }
            
            int l, r;
            int state_l = false, state_r = false;
            if(tmp->left){
                l = helper(tmp->left);
                state_l = true;
            }else{
                l = 0;
            }
            
            if(tmp->right){
                r = helper(tmp->right);
                state_r = true;
            }else{
                r = 0;
            }
            
            int max_num = tmp->val;
            
            if(tmp->val+l+r > tmp->val+l && tmp->val+l+r > tmp->val+r){
                if(tmp->val+l+r > ans){
                    ans = tmp->val+l+r;
                }
            }
            if(r > max_num && state_r){
                if(r > ans){
                    ans = r;
                }
            }
            if(l > max_num && state_l){
                if(l > ans){
                    ans = l;
                }
            }
            
            if(tmp->val+l > max_num && state_l){
                max_num = tmp->val + l;
            }
            if(tmp->val+r > max_num && state_r){
                max_num = tmp->val + r;
            }
            
    
            return max_num;
        }
    public:
        int maxPathSum(TreeNode* root) { 
            ans = root->val;
            return max(helper(root), ans);
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5NjAwMTM3_size_16_color_FFFFFF_t_70]: /images/20220213/f4fb0fd75e7943bfb543f52d821083e5.png