【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);
    }
};