程序员代码面试指南 3.7：找到二叉树中的最大搜索二叉子树

1、思路

• 需要求出以每一个节点为头节点的子树的最大搜索二叉子树。对于每一个节点，我们用一个结构体ReturnType来保存该节点的四种信息：
  1、maxBSTHead 该子树中最大二叉搜索树的头节点；
  2、maxBSTSize 该子树中最大二叉搜索树的节点个数；
  3、min 该子树中最小节点值；
  4、max 该子树中最大节点值；

• 以节点 root 为头节点的子树中，最大搜索二叉子树只可能有三种情况：
  1、最大搜索二叉子树是root左子树中的最大搜索二叉子树，即答案来自左子树；
  2、最大搜索二叉子树是root右子树中的最大搜索二叉子树，即答案来自右子树；
  3、最大搜索二叉子树是以root为头节点的子树，即答案来自root子树；

• 先收集左子树信息，然后是右子树信息，最后在头节点做信息整合。由于是后序遍历，故时间复杂度为 。

2、代码

#include 
#include 

using namespace std;

struct TreeNode         //二叉树节点
{
    int val;
    TreeNode *left, *right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

struct ReturnType       //节点信息
{
    TreeNode *maxBSTHead;
    int maxBSTSize;
    int min;
    int max;

    ReturnType(TreeNode *_maxBSTHead, int _maxBSTSize, int _min, int _max) : 
                maxBSTHead(_maxBSTHead), maxBSTSize(_maxBSTSize), min(_min), max(_max) {}
};

void createTree(TreeNode *root, int &n)         //建树
{
    if (n == 0) return;

    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    root->val = rootVal;
    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left, -- n);
    }
    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right, -- n);
    }
}

ReturnType* process(TreeNode *root)
{
    if (root == nullptr)                        //处理空节点
    {
        return new ReturnType(nullptr, 0, INT_MAX, INT_MIN);
    }

    ReturnType *leftData = process(root->left); //取得左右子树节点的信息
    ReturnType *rightData = process(root->right);

    //更新四种信息值
    int _min = min(root->val, min(leftData->min, rightData->min));
    int _max = max(root->val, max(leftData->max, rightData->max));
    int _maxBSTSize = max(leftData->maxBSTSize, rightData->maxBSTSize);
    TreeNode *_maxBSTHead = leftData->maxBSTSize >= rightData->maxBSTSize ? 
                            leftData->maxBSTHead : rightData->maxBSTHead;

    //特判以当前节点 root 为头节点的二叉树是否为二叉搜索树
    if (leftData->maxBSTHead == root->left && rightData->maxBSTHead == root->right 
        && root->val > leftData->max && root->val min)
    {
        _maxBSTSize = leftData->maxBSTSize + rightData->maxBSTSize + 1;
        _maxBSTHead = root;
    }

    return new ReturnType(_maxBSTHead, _maxBSTSize, _min, _max);
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode *root = new TreeNode(0);
    createTree(root, n);

    ReturnType *res = process(root);
    cout maxBSTSize << endl;

    return 0;
}