C++ Simple Solution, Concise Code With Explanation


  • 0

    Similar thought with binary-tree-maximum-path-sum
    Time O(n)
    Space O(n)

    A legal binary search tree must have those points:

    1. left and right son trees are legal bst
    2. left son tree's largest num < cur->val < right son tree's smallest num
    class Solution {
        int helper(TreeNode* cur) {
            if (!cur)
                return 0;
            int l = helper(cur->left), r = helper(cur->right);
            if (l < 0 || r < 0)
                return -1;
            TreeNode* left = cur->left, *right = cur->right;
            while (left && left->right)
                left = left->right;
            while (right && right->left)
                right = right->left;
            if ((!left || left->val < cur->val) && (!right || right->val > cur->val) ) {
                res = max(res, l + r + 1);
                return l + r + 1;
            }
            return -1;
        }
        int res;
    public:
        int largestBSTSubtree(TreeNode* root) {
            res = 0;
            helper(root);
            return res;
        }
    };
    

Log in to reply
 

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