【leetcode】333 最大BST子树（二叉树，递归，树形DP）

题目链接：https://leetcode-cn.com/problems/largest-bst-subtree/

题目描述

给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，其中最大指的是子树节点数最多的。

注意:

子树必须包含其所有后代。

示例:

输入: [10,5,15,1,8,null,7]

   10 
   / \ 
  *5  15 
 / \   \ 
*1  *8   7

输出: 3
解释: 加*部分为最大的 BST 子树。
     返回值 3 在这个样例中为子树大小。
           

进阶:

你能想出用 O(n) 的时间复杂度解决这个问题吗？

思路

利用递归函数设计一个二叉树后序遍历的过程：

（1）先遍历左子树收集信息

（2）遍历右子树收集信息

（3）在根节点做信息整合

以节点root为根节点的子树中，最大BST有以下3种情况：

（1）以节点root为根节点的子树中，最大BST就是root的左子树中的最大BST

（2）以节点root为根节点的子树中，最大BST就是root的右子树中的最大BST

（3）如果root左子树的最大BST是左子树全体，root右子树的最大BST是右子树全体，并且root的值大于左子树所有节点最大值，root的值小于右子树所有节点的最小值。则root为跟姐的最大BST子树就是root全体子树；即用root将左右子树链接起来

因为是后序遍历，时间复杂度为O（n）

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class ReturnType{
public:
    TreeNode *maxBSTRoot;   // 最大BST子树根节点
    int maxBSTSize;         // 最大BST子树节点数
    int min;                // 树节点最小值
    int max;                // 树节点最大值
    ReturnType(TreeNode* maxBSTRoot, int maxBSTSize, int min, int max ){
        this->maxBSTRoot = maxBSTRoot;
        this->maxBSTSize = maxBSTSize;
        this->min = min;
        this->max = max;
    }
};
class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        return helper(root).maxBSTSize;
    }

private:
    // 处理函数
    ReturnType helper(TreeNode *root){
        // 空树
        if(!root)
            return ReturnType(nullptr,0,INT_MAX,INT_MIN);

        ReturnType lData = helper(root->left);  // 左树信息
        ReturnType rData = helper(root->right); // 右树信息
        // 信息整合 root为根节点的子树的最小值
        int minVal = min(root->val, min(lData.min, rData.min));
        int maxVal = max(root->val, max(lData.max, rData.max));

        // 情况1，2：最大BST存在与其左子树或者右子树其中一个
        //          更新参数
        TreeNode *maxBSTRoot = lData.maxBSTSize >= rData.maxBSTSize ? lData.maxBSTRoot : rData.maxBSTRoot;
        int maxBSTSize = max(lData.maxBSTSize, rData.maxBSTSize);

        // 情况3：root左子树是以左孩子为根节点的最大BST，root右子树是以右孩子为根节点的最大BST
        //       并且root左子树最大值 < root值 < 右子树最小值
        if(lData.maxBSTRoot == root->left && rData.maxBSTRoot == root->right
            && lData.max < root->val && rData.min > root->val){
            maxBSTSize = lData.maxBSTSize + rData.maxBSTSize + 1;
            maxBSTRoot = root;
        }

        return ReturnType(maxBSTRoot,maxBSTSize, minVal, maxVal);
    }
};