Leetcode 333. Largest BST Subtree (二叉树后序遍历好题)

333. Largest BST Subtree
     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.

Example:

Input: [10,5,15,1,8,null,7]

10
/
5 15
/ \
1 8 7

Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree’s size, which is 3.
Follow up:
Can you figure out ways to solve it with O(n) time complexity?

Difficulty:
Medium

解法1：后序遍历
这题要注意的是区分空节点和不符合BST性质的节点。
空节点也算BST树，要返回{INT_MAX, INT_MIN, 0}, 但不符合BST性质的节点就必须返回{}。

/*
    Following is Binary Tree Node structure:
    class TreeNode
    {
    public:
        int data;
        TreeNode *left, *right;
        TreeNode() : data(0), left(NULL), right(NULL) {}
        TreeNode(int x) : data(x), left(NULL), right(NULL) {}
        TreeNode(int x, TreeNode *left, TreeNode *right) : data(x), left(left), right(right) {}
    };
*/
int maxCount = 0;
vector<int> helper(TreeNode *root) {
    if (!root) return {INT_MAX, INT_MIN, 0};
    vector<int> left = helper(root->left); //<min, max, count> of left subtree
    vector<int> right = helper(root->right); //<min, max, count> of right subtree
    if (left.size() > 0 && root->data > left[1] && 
        right.size() > 0 && root->data < right[0]) {
        maxCount = max(maxCount, left[2] + right[2] + 1);
        return {min(left[0], root->data), max(right[1], root->data), left[2] + right[2] + 1};
    }

    return {};
}

int largestBST(TreeNode * root){
    // Write your code here.
    if (!root) return 0;
    helper(root);
    return maxCount;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33