Leetcode 333 - largest BST subtree - study code from the blog: http://www.cnblogs.com/grandyang/p/5188938.html

Leetcode333_LargestBSTSubtree_studyCode.cpp

/*
Leetcode 333: Largest BST subtree

http://www.cnblogs.com/grandyang/p/5188938.html

Julia likes to review the third algorithm with time complexity O(n). 

*** depth first search ***

题目中的Follow up让我们用O(n)的时间复杂度来解决问题，我们还是采用 DFS 的思想来解题，由于时间复杂度的限制，只允许
我们遍历一次整个二叉树，由于满足题目要求的二叉搜索子树必定是有叶节点的，所以我们的思路就是先递归到最左子节点，
然后逐层往上递归，对于每一个节点，我们都记录当前最大的 BST 的节点数，当做为左子树的最大值，和做为右子树的最小值，
当每次遇到左子节点不存在或者当前节点值大于左子树的最大值，且右子树不存在或者当前节点值小于右子树的最小数时，说明
 BST 的节点数又增加了一个，我们更新结果及其参数，如果当前节点不是 BST 的节点，那么我们更新 BST 的节点数 res 为左右子
节点的各自的 BST 的节点数的较大值，参见代码如下：
*/
class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        int res = 0, mn = INT_MIN, mx = INT_MAX;
        bool d = isValidBST(root, mn, mx, res);
        return res;
    }
    
    bool isValidBST(TreeNode *root, int &mn, int &mx, int &res) {
        if (!root) return true;
        
        int left_n = 0, right_n = 0, left_mn = INT_MIN;
        
        int right_mn = INT_MIN, left_mx = INT_MAX, right_mx = INT_MAX;
        
        bool left  = isValidBST(root->left, left_mn, left_mx, left_n);
        bool right = isValidBST(root->right, right_mn, right_mx, right_n);
        
        if (left && right) {
            if ((!root->left || root->val > left_mx) && (!root->right || root->val < right_mn)) 
            {
                res = left_n + right_n + 1;
                mn  = root->left ?  left_mn  : root->val;
                mx  = root->right ? right_mx : root->val;
                
                return true;
            }
        }
        
        res = max(left_n, right_n);
        
        return false;
    }
};