【二叉树重点】求二叉树的最大搜索子树

题目

给定一棵二叉树，其中所有节点的值都不一样,找到含有节点最多的搜索二叉子树,并返回这棵子树的头节点。

思路

二叉搜索树的性质：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。

需要后序递归遍历二叉树，才能从下到上不断更新以当前节点为根节点的子树中的最大搜索子树。

2、设当前头结点为h，如果以h->left为根节点的左子树是一棵搜索二叉树，以h->right为根节点的右子树是一棵搜索二叉树，并且h的节点值大于以h-left为根节点的左子树中的最大值，同时h的节点值小于以h-right为根节点的右子树中的最大值，则最大搜索二叉树以h为头结点。

3、如果不满足2中的情况，则最大搜索二叉树取以h->left为根节点的子树中最大搜索二叉树与以h->right为根节点的子树中最大搜索二叉树里面节点最多的那个。

步骤

1、后序递归遍历二叉树

2、设计递归函数：设当前遍历节点为cur，遍历cur 的左子树收集4个信息：左子树上最大搜索二叉树的头结点，左子树上节点的最大值，最小值和节点个数；遍历cur 的右子树收集4个信息：右子树上最大搜索二叉树的头结点，右子树上节点的最大值，最小值和节点个数。

3、判断2中信息是否满足cur为根节点的二叉树是一棵搜索二叉树，如果满足，则返回cur节点，否则返回左子树和右子树的最大搜索二叉树中，节点数较多的那棵树的头节点。

4、重点是在一个递归过程中收集4个信息，对其进行整合组织之后将其传回到上一层。可以用全局变量更新或返回长度为4的数组。

代码实现

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class MaxSubtree {
public:
    TreeNode *postTraverse(TreeNode* root,int &maxnode,int &minnode,int &num){//maxnode为以root为根节点的树中的最大值
        if(root == NULL){
           maxnode  = -99999;
           minnode = 99999;
           num = 0;
           return NULL;
        }
        int lmin,lmax,lnum;
         TreeNode* ld = postTraverse(root->left,lmax,lmin,lnum);
        int rmin,rmax,rnum;
         TreeNode* rd = postTraverse(root->right,rmax,rmin,rnum);
        maxnode = max(rmax,root->val);
        minnode = min(lmin,root->val);
        if(root->val >= lmax &&root->val <= rmin && rd==root->right &&ld == root->left){
            num = lnum + rnum+1;//当前节点大于左边子树最大搜索树的最大值，小于右边子树最大搜索树的最小值
            return root;
        }
        if(lnum>rnum){
            num = lnum;
            return ld;
        }
        else{
            num = rnum;
            return rd;
        }
    }
    TreeNode* getMax(TreeNode* root) {
        // write code here
       if(root == NULL)
           return NULL;
       int maxnode,minnode,num;
       TreeNode *result = postTraverse(root,maxnode,minnode,num);
       return result;
       
    }
};