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。對(duì)于當(dāng)前node，左子樹(shù)最大節(jié)點(diǎn)值 < node.val，右子樹(shù)最小節(jié)點(diǎn)值 > node.val。
2. 計(jì)算數(shù)目。當(dāng)前節(jié)點(diǎn)的最大數(shù)目為左右子樹(shù)中最大的，如果左右子樹(shù)同時(shí)滿(mǎn)足都為BST，并且當(dāng)前節(jié)點(diǎn)的樹(shù)也滿(mǎn)足BST。則最大數(shù)目為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);
    }
};