leetcode：333. 最大 BST 子树

题目来源

• leetcode：largest-bst-subtree

题目描述

题目解析

题目大概意思是：

• 给定一个二叉树，整体可能是，也可能不是二叉搜索树，但是它一定有子树是二叉搜索树，要找到节点数最多的子搜索二叉树的节点数

所以，本题需要解决两个问题：

• 找出二叉树中所有为BST的子树
• 返回最大的那个BST子树的节点数

这个最大的子搜索二叉树，有两种可能性：包含二叉树头节点，不包含二叉树头结点。

• 不包含头结点时：就需要知道左子树的最大搜索二叉树的节点数，右子树的最大搜索二叉树的节点数
• 包含头结点时：需要判断左树是不是搜索二叉树，右树是不是搜索二叉树，左树的最大值是否小于头节点，右树的最小值是否大于头节点，同时还需要左树和右树的节点数。

也就是说，root每次都需要问一问左子树和右子树：

• 最大满足二叉搜索树条件的子树有多少节点数
• 整个子树有多少节点数，整个子树的最大值、最小值是多少
• 是不是二叉搜索树

又因为，当最大搜索二叉树的节点数和节点数相等就意味着整个子树是搜索二叉树，所以可以化简为最大搜索二叉树的节点数、max、min、节点数。

所以，定义一个辅助类：

 struct Info{
    
        int maxBSTSubtreeSize;
        int allSize;
        int max;
        int min;

        explicit Info(int m, int a, int ma, int mi) {
    
            maxBSTSubtreeSize = m;
            allSize = a;
            max = ma;
            min = mi;
        }
    };

递归求解当前子树的info：

	std::shared_ptr<Info> process(TreeNode *root){
    
        if(root == nullptr){
    
            return nullptr;
        }

        // 获取左右子树信息
        auto leftInfo = process(root->left);
        auto rightInfo = process(root->right);
        // 拼凑自己的信息
        int max = root->val, min = root->val, allSize = 1;
        if(leftInfo != nullptr){
    
            max = std::max(max, leftInfo->max);
            min = std::min(min, leftInfo->min);
            allSize += leftInfo->allSize;
        }
        if(rightInfo != nullptr){
    
            max = std::max(max, rightInfo->max);
            min = std::min(min, rightInfo->min);
            allSize += rightInfo->allSize;
        }

        // [左|右]树 最大搜索二叉树大小
        int p1 = -1, p2 = -1;
        if(leftInfo != nullptr){
    
            p1 = leftInfo->maxBSTSubtreeSize;
        }
        if(rightInfo != nullptr){
    
            p2 = rightInfo->maxBSTSubtreeSize;
        }

        // 是否包含头节点
        int p3 = -1;
        bool leftSearch = leftInfo == nullptr || leftInfo->maxBSTSubtreeSize == leftInfo->allSize;   // 左树是否是搜索二叉树
        bool rightSearch = rightInfo == nullptr || rightInfo->maxBSTSubtreeSize == rightInfo->allSize;  // 右树是否是搜索二叉树
        if(leftSearch && rightSearch){
    
            bool  lessMaxLessX = leftInfo == nullptr || leftInfo->max < root->val;     // 左树最大值是否比当前节点值小（空也认为比当前节点小）
            bool  rightMinMoreX = rightInfo == nullptr || rightInfo->min > root->val;  // 右树最小值是否比当前节点值大（空也认为比当前节点大）
            // 都满足，才能修改p3的值
            if (lessMaxLessX && rightMinMoreX) {
    
                int leftSize = leftInfo == nullptr ? 0 : leftInfo->allSize;
                int rightSize = rightInfo == nullptr ? 0 : rightInfo->allSize;
                p3 = leftSize + rightSize + 1;
            }
        }

        // 最后修改，当前子树最大搜索二叉子树的大小
        int maxSubSize = std::max(p1,  std::max(p2, p3));
        return std::make_shared<Info>(maxSubSize, max, min, allSize);
    }

调用上面方法获取结果：

    int maxSubSearchBinaryTreeSize(TreeNode *root){
    
        if(root == nullptr){
    
            return 0;
        }
        return process(root)->maxBSTSubtreeSize;
    }

小结

二叉树递归套路总结：

• 1）假设以X节点为头，假设可以向X左树和X右树要任何信息
• 2）在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要）
• 3）列出所有可能性后，确定到底需要向左树和右树要什么样的信息
• 4）把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S
• 5）递归函数都返回S，每一棵子树都这么要求
• 6）写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息