Problem

More LeetCode Discussions

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:
A subtree must include all of its descendants.
Here's an example:

    10
    / \
   5  15
  / \   \ 
 1   8   7

The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree's size, which is 3.

Solution

1. 判断是否是BST。对于当前node，左子树最大节点值 < node.val，右子树最小节点值 > node.val。
2. 计算数目。当前节点的最大数目为左右子树中最大的，如果左右子树同时满足都为BST，并且当前节点的树也满足BST。则最大数目为leftSize + rightSize + 1。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int largestBSTSize(TreeNode *node, int &minV, int &maxV, bool &isTree) {
        if (node == NULL) {
            isTree = true;
            return 0;
        }    
        
        int leftMaxV = INT_MIN;
        int leftMinV = INT_MAX;
        bool leftIsTree = true;
        int leftSize = largestBSTSize(node->left, leftMinV, leftMaxV, leftIsTree);
        
        int rightMinV = INT_MAX;
        int rightMaxV = INT_MIN;
        bool rightIsTree = true;
        int rightSize = largestBSTSize(node->right, rightMinV, rightMaxV, rightIsTree);
        
        int maxSize = max(leftSize, rightSize);
        
        if (leftMaxV < node->val && node->val < rightMinV && leftIsTree && rightIsTree) {
            maxSize = leftSize + rightSize + 1;
            isTree = true;
        } else {
            isTree = false;
        }
        
        maxV = max(max(leftMaxV, rightMaxV), node->val);
        minV = min(min(leftMinV, rightMinV), node->val);
        
        return maxSize;
    }
    
    int largestBSTSubtree(TreeNode* root) {
        int maxV;
        int minV;
        bool isTree;
        return largestBSTSize(root, minV, maxV, isTree);
    }
};