1373. Maximum Sum BST in Binary Tree

這題hard題其實蠻有趣的, 解題的想法是

每個節點會回傳四個東西

這個節點是否是binary tree

包含這個節點的總和

這個節點Tree的最小值,

最大值

假設我檢查左右兩邊的子樹, 若不是binary tree, 基本上就可以放棄這個點了, 直接回傳false.

如果他左右沒問題, 我們需要去檢查, 左邊的最小值最大值, 跟右邊的最小值最大值

你沒看做, 無論是哪一邊, 最小值跟最大值都需要, 這也是這題的精隨

以左子樹為例

最大值是用來跟當前的node value,進行比對

最小值則是你要拿來向上呈報的

所以這樣遞迴才能完整

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    pair<bool, vector<int>> dfs(TreeNode *root, int &res){
        
        pair<bool, vector<int>> left;
        int sum_value = 0;
        int min_value = root->val;
        int max_value = root->val;
        sum_value+=root->val;
        bool flag = true;
        if(root->left){
            left = dfs(root->left, res);
            if(!left.first || left.second[1] >= root->val){
               flag = false;
            }
            sum_value += left.second[2];
            min_value = left.second[0];
        }
        pair<bool, vector<int>> right;
        if(root->right){
            right = dfs(root->right, res);
            if(!right.first || right.second[0] <= root->val){
                flag = false;
            }
            sum_value += right.second[2];
            max_value = right.second[1];
        }
       
        if(flag){
            res = max(res, sum_value);
        }
      
        return {flag, {min_value, max_value,sum_value}};
    }
    int maxSumBST(TreeNode* root) {
        int res = 0;
        dfs(root, res);
        
        return res;
    }
};