c++ o(n) clean and easy


  • 0
    T

    Share my O(n) solution with C++11 clean and easy understand.

     class Solution {
    public:
        int largestBSTSubtree(TreeNode* root) {
            int res = 0;
            dfs(root, res);
            return res;
        }
         inline auto dfs(TreeNode* root,int& maxVal) -> tuple<int,int,int,int>{
            if(!root) return {1,0,INT_MAX,INT_MIN};
            auto item_1 = dfs(root->left,maxVal);
            auto item_2 = dfs(root->right,maxVal);
            if (!get<0>(item_1) || !get<0>(item_2) || 
                       root->val <= get<3>(item_1) || root->val > get<2>(item_2)){
                return {0,0,0,0};
            }
            int maxNode = get<1>(item_1) + get<1>(item_2) + 1;
            maxVal = max(maxVal, maxNode);
            return {1,maxNode,min(root->val,get<2>(item_1)),max(root->val,get<3>(item_2))};     
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.