1、题目

给定一棵二叉树的根节点 root，返回这棵二叉树中最大的二叉搜索子树的大小

2、分析

一棵二叉树可能它不是二叉搜索树，但是它的子树可能是二叉搜索树。

使用二叉树的递归套路。

①目标：求 X 为根节点的二叉树的最大二叉搜索子树的节点数。

②可能性：

1）X 不做根的情况：
（1）结果在左树上，左树上的maxBSTSubTreeSize；
（2）结果在右树上，右树上的maxBSTSubTreeSize;

2）X 做根的情况。那么整棵树都是BST，需要证明该树是BST，则需要向左右树获取的信息：（1）左树是不是BST；
（2）右树是不是BST；
（3）左树的max < x；
（4）右树的min > x；
（5）左树的size + 右树的size + 1。

整理所有条件的并集可得需要的信息：
（1）maxBSTSubTreeSize;
（2）是否为BST
（3）max
（4）min
（5）size
但是可以化简，如果maxBSTSubTreeSize 和 size 是相等的，那么整棵树就是BST，所以（2）这个信息可以不要。

3、实现

C++ 版

//暂未提交验证
/*************************************************************************
	> File Name: 038.返回二叉树最大二叉搜索子树的大小.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 六  7/ 2 12:47:20 2022
 ************************************************************************/

#include <iostream>
using namespace std;

class TreeNode {
public:
    int value;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int data) : value(data) {}
};

class Info {
public:
    int maxBSTSubTreeSize;//最大搜索二叉树的节点数
    int maxVal; //树的最大值
    int minVal; //树的最小值
    int allSize; //树的节点数

    Info(int mbs, int ma, int mi, int all) : 
        maxBSTSubTreeSize(mbs), maxVal(ma), minVal(mi), allSize(all) {}
};

Info *process(TreeNode *x) {
    if (x == nullptr) {
        return nullptr;
    }

    Info *leftInfo = process(x->left);
    Info *rightInfo = process(x->right);

    int maxVal = x->value;
    int minVal = x->value;
    int allSize = 1;
    int p1 = -1;
    int p2 = -1;
    int p3 = -1;
    if (leftInfo != nullptr) {
        maxVal = max(maxVal, leftInfo->maxVal);
        minVal = min(minVal, leftInfo->minVal);
        allSize += leftInfo->allSize;
        //可能性1：答案在左树
        p1 = leftInfo->maxBSTSubTreeSize;
    }

    if (rightInfo != nullptr) {
        maxVal = max(maxVal, rightInfo->maxVal);
        minVal = min(minVal, rightInfo->minVal);
        allSize += rightInfo->allSize;
        //可能性2：答案在右树
        p2 = rightInfo->maxBSTSubTreeSize;
    }
    
    //可能性3：整棵树是BST
    bool leftBST = leftInfo == nullptr ? true : leftInfo->maxBSTSubTreeSize == leftInfo->allSize;
    bool rightBST = rightInfo == nullptr ? true : rightInfo->maxBSTSubTreeSize == rightInfo->allSize;
    if (leftBST && rightBST) {
        bool legalLeft = leftInfo == nullptr ? true : leftInfo->maxVal < x->value;
        bool legalRight = rightInfo == nullptr ? true : rightInfo->minVal > x->value;
        if (legalLeft && legalRight) {
            p3 = (leftInfo == nullptr ? 0 : leftInfo->allSize) + (rightInfo == nullptr ? 0 : rightInfo->allSize) + 1;
        }
    }
    
    int maxBSTSubTreeSize = max(max(p1, p2), p3);

    return new Info(maxBSTSubTreeSize, maxVal, minVal, allSize);
}

int largestBSTSubTree(TreeNode *root) {
    if (root == nullptr) return 0;

    return process(root)->maxBSTSubTreeSize;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

Java 版

public class MaxSubBSTSize {
    public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int value) {
			this.value = value;
		}
	}

    public static int largestBSTSubtree(Node head) {
		if (head == null) {
			return 0;
		}
		return process(head).maxBSTSubTreeSize;
	}

    public static class Info {
        public int maxBSTSubTreeSize; //最大搜索二叉树的节点数
        public int allSize; //树的节点数
        public int max; //树的最大值
        public int min; //树的最小值

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

    public static Info process(Node x) {
        if (x == null) return null;

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int max = x.value;
        int min = x.value;
        int allSize = 1; //节点x本身
        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
            min = Math.max(leftInfo.min, min);
            allSize += leftInfo.allSize;
        }
        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
            min = Math.max(rightInfo.min, min);
            allSize += rightInfo.allSize;
        }

        int p1 = -1;
        if (leftInfo != null) { //可能性1：左树的maxBSTSubTreeSize
            p1 = leftInfo.maxBSTSubTreeSize;
        }
        int p2 = -1;
        if (rightInfo != null) { //可能性2
            p2 = rightInfo.maxBSTSubTreeSize;
        }
        //可能性3：X为根
        int p3 = -1;
        //左树是否为BST
        boolean leftBST = leftInfo == null ? true : (leftInfo.maxBSTSubTreeSize == leftInfo.allSize);
        //右树是否为BST
        boolean rightBST = rightInfo == null ? true : (rightInfo.maxBSTSubTreeSize == rightInfo.allSize);
        if (leftBST && rightBST) {
            //左树的max 是否 小于 x
            boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.value);
            //右树的min 是否 大于 x
            boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.value);
            if (leftMaxLessX && rightMinMoreX) {
                int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
                int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
                p3 = leftSize + rightSize + 1;
            }
        }

        int maxBSTSubTreeSize = Math.max(Math.max(p1, p2), p3);
         
        return new Info(maxBSTSubTreeSize, allSize, max, min);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83