【题目】
给定一棵二叉树的头节点head，请返回最大搜索二叉子树的大小
【题解】
简化问题，想到该问题的解答应该有几种情形
第一种可能：
最大搜索二叉子树在head的左子树
第二种可能：
最大搜索二叉子树在head的右子树
第三种可能：
最大搜索二叉子树为自己；利用左子树的最大值与右子树的最小值
递归左子树，再递归右子树
信息1：左子树中最大搜索二叉树的大小
信息2：右子树中最大搜索二叉树的大小
信息3：左子树最大搜索二叉树的头结点
信息4：右子树最大搜索二叉树的头结点
信息5：左子树上的最大值
信息6：右子树上的最小值
使用递归，求每一个结点所包含的最大搜索二叉树
【代码】
1 #pragma once 2 #include3 #include 4 #include 5 6 using namespace std; 7 8 struct Node 9 { 10 int val; 11 Node* l; 12 Node* r; 13 Node(int a) :val(a), l(nullptr), r(nullptr) {} 14 }; 15 16 //递归方式一 17 struct returnType 18 { 19 int size; 20 Node* head; 21 int min; 22 int max; 23 returnType(int s, Node* h, int mi, int ma) :size(s), head(h), min(mi), max(ma) {} 24 }; 25 26 returnType* findSTree1(Node* head) 27 { 28 if (head == nullptr) 29 return new returnType(0, nullptr, INT_MAX, INT_MIN); 30 returnType* lInfo = findSTree1(head->l);//得到左子树的最大搜索二叉树 31 returnType* rInfo = findSTree1(head->r);//得到右子树的最大搜索二叉树 32 33 int selfSize = 0;//判断包含该头节点的整棵树是否为搜索二次树 34 if (lInfo->head == head->l && 35 rInfo->head == head->r && 36 lInfo->max < head->val && 37 rInfo->min > head->val 38 ) 39 selfSize = lInfo->size + 1 + rInfo->size; 40 41 int maxSize = max(max(lInfo->size, rInfo->size), selfSize);//求得最大的搜索二叉树的大小 42 Node* maxHead = nullptr;//选择最大的子树的头结点 43 if (maxSize == selfSize) 44 maxHead = head; 45 else if (maxSize == lInfo->size) 46 maxHead = lInfo->head; 47 else 48 maxHead = rInfo->head; 49 50 //这时返回的是包含head的整颗子树 51 return new returnType(maxSize, maxHead, 52 min(min(lInfo->min, rInfo->min), head->val), 53 max(max(lInfo->max, rInfo->max), head->val)); 54 } 55 56 57 //使用第二种递归 58 59 Node* findSTree2(Node* head, vector &info) 60 { 61 if (head == nullptr) 62 { 63 info[0] = 0; 64 info[1] = INT_MIN; 65 info[2] = INT_MAX; 66 return nullptr; 67 } 68 vector hv = info; 69 //得到左右子树的信息 70 Node* lNode = findSTree2(head->l, info); 71 vector lv = info; 72 Node* rNode = findSTree2(head->r, info); 73 vector rv = info; 74 //更新信息 75 info[1] = max(max(lv[1], rv[1]), head->val); 76 info[2] = min(min(lv[2], rv[2]), head->val); 77 //判断 78 if (lNode == head->l && rNode == head->r && lv[1] < head->val && rv[2] > head->val) 79 { 80 info[0] = lv[0] + rv[0] + 1; 81 return head; 82 } 83 info[0] = max(lv[0], rv[0]); 84 return lv[0] > rv[0] ? lNode : rNode; 85 } 86 87 88 int maxSTree(Node* head) 89 { 90 vector info(3,0);//储存字数的大小、最大值、最小值 91 findSTree2(head, info); 92 return info[0]; 93 } 94 95 96 97 98 void Test() 99 {100 Node* root = new Node(9);101 root->l = new Node(8);102 root->r = new Node(1);103 root->l->l = new Node(5);104 root->l->r = new Node(9);105 root->l->l->l = new Node(4);106 root->l->l->r = new Node(6);107 root->r->l = new Node(5);108 root->r->r = new Node(3);109 returnType* p = findSTree1(root);110 cout << p->size << endl;111 112 root = nullptr;113 root = new Node(5);114 root->l = new Node(2);115 root->r = new Node(6);116 root->l->l = new Node(1);117 root->l->r = new Node(3);118 p = findSTree1(root);119 cout << p->size << endl;120 121 root = nullptr;122 root = new Node(9);123 root->l = new Node(8);124 root->r = new Node(1);125 root->l->l = new Node(5);126 root->l->r = new Node(9);127 root->l->l->l = new Node(4);128 root->l->l->r = new Node(6);129 root->r->l = new Node(5);130 root->r->r = new Node(3);131 cout << maxSTree(root) << endl;132 133 root = nullptr;134 root = new Node(5);135 root->l = new Node(2);136 root->r = new Node(6);137 root->l->l = new Node(1);138 root->l->r = new Node(3);139 cout << maxSTree(root) << endl;140 141 142 143 }