C++_O(n)_Bottom To Top method_with brief explanation


  • 0

    Here we use bottom-to-top to traverse the Binary Tree. Now suppose you have a tree, now you are at the leaf node. So for each node, you will definitely construct a BST, for these leaves nodes parents, they should follow these rules:

    1. root->val > max_value of left node,
    2. root->val < min_value of right node.
      So we can use these constraints to judge whether their parents can construct BSTs, if so, we can "merge" them into a larger node, which contains information of (number of nodes in these larger node, min_value, max_value).

    Also we should set a variable to count our current max_number of our largest BST. Each time we successfully construct a BST, we update the value of this variable.

    Repeat these step to our root value.

    class Solution {
    public:
    int largestBSTSubtree(TreeNode* root) {
        if(root == nullptr) return 0;
        long res = 0;
        dfs(root, res);
        return res;
    }
    vector<long> dfs(TreeNode* root, long& res){
        //NULL point means that we are now reaching beyond our leaf node, in order to make our leaf as a BST, we should set Max = LONG_MIN, Min = LONG_MAX;
        if(root == nullptr) return {0, LONG_MAX, LONG_MIN};
        auto L = dfs(root->left, res);
        auto R = dfs(root->right, res);
        if(root->val > L[2] && root->val < R[1]){
            res = max(res, 1 + L[0] + R[0]);//update our result.
            
            //merge into a larger node
            L[1] = min(L[1], (long)root->val);
            R[2] = max(R[2], (long)root->val);
            return {1 + L[0] + R[0], L[1], R[2]};
        }
        return {0, LONG_MIN, LONG_MAX};
    }
    };

Log in to reply
 

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