【题目】

给定一棵二叉树的头节点head，请返回最大搜索二叉子树的大小

【要求】

如果节点数为N，要求时间复杂度为O（），额外空间复杂度为O（h），h为二叉树的高度。

【题解】

以节点node为头的树中，最大的搜索二叉子树只可能来自以下两种情况。

第一种：如果来自node左子树上的最大搜索二叉子树是以node.left为头的；来自node右子树上的最大搜索二叉子树是以node.right为头的；node左子树上的最大搜索二叉子树的最大值小于node.value；node右子树上的最大搜索二叉子树的最小值大于node.value，那么以节点node为头的整棵树都是搜索二叉树。

第二种：如果不满足第一种情况，说明以节点node为头的树整体不能连成搜索二叉树。

这种情况下，以node为头的树上的最大搜索二叉子树是来自node的左子树上的最大搜索二叉子树和来自node的右子树上的最大搜索二叉子树之间，节点数较多的那个。

通过以上分析，求解的具体过程如下：

1.整体过程是二叉树的后序遍历。

2.遍历到当前节点记为cur时，先遍历cur的左子树收集4个信息，分别是左子树上最大搜索二叉子树的头节点（IBST）、节点数（lSize）、最小值（lMin）和最大值（lMax）。

再遍历cur的右子树收集4个信息，分别是右子树上最大搜索二叉子树的头节点（rBST）、节点数（rSize）、最小值（rMin）和最大值（rMax）。

3.根据步骤2所收集的信息，判断是否满足第一种情况，如果满足第一种情况，就返回cur节点，如果满足第二种情况，就返回IBST和rBST中较大的一个。

4.可以使用全局变量的方式实现步骤2中收集节点数、最小值和最大值的问题。

找到最大搜索二叉子树的具体过程请参看如下代码中的biggestSubBST方法。

 

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 using namespace std;  6 struct Node  7 {  8     int val;  9     Node *l, *r; 10     Node(int a = -1) :val(a), l(nullptr), r(nullptr) {} 11 }; 12 Node* createTree() 13 { 14     Node* root = new Node(6); 15     root->l = new Node(1); 16     root->r = new Node(12); 17     root->l->l = new Node(0); 18     root->l->r = new Node(3); 19     root->r = new Node(12); 20     root->r->l = new Node(10); 21     root->r->r = new Node(13); 22     root->r->l->l = new Node(4); 23     root->r->l->r = new Node(14); 24     root->r->l->l->l = new Node(2); 25     root->r->l->l->r = new Node(5); 26     root->r->l->r->l = new Node(11); 27     root->r->l->r->r = new Node(15); 28     root->r->r->l = new Node(20); 29     root->r->r->r = new Node(16); 30     return root; 31 } 32 /// 33 int inOrder(Node* root, vector
         
          &in) 34 { 35     if (root == nullptr) 36         return 0; 37     int ln = inOrder(root->l, in); 38     in.push_back(root->val); 39     int rn = inOrder(root->r, in); 40     return ln + 1 + rn; 41 } 42  43 void solve01(Node* root) 44 { 45     Node* res = new Node(); 46     int maxN = -1; 47     queue
          
           q; 48 q.push(root); 49 while (!q.empty()) 50 { 51 Node* p = q.front(); 52 q.pop(); 53 vector
           
            tempV, V; 54 int tempN = inOrder(p, V);//子树个数 55 tempV = V; 56 sort(V.begin(), V.end()); 57 if (tempV == V && maxN < tempN) 58 { 59 maxN = tempN; 60 res = p; 61 } 62 if (p->l != nullptr) 63 q.push(p->l); 64 if (p->r != nullptr) 65 q.push(p->r); 66 } 67 cout << maxN << " " << res->val << endl; 68 } 69 // 70 Node* posOrder(Node* root, int* record) 71 { 72 if (root == nullptr) 73 { 74 record[0] = 0; 75 record[1] = INT32_MAX; 76 record[2] = INT32_MIN; 77 return nullptr; 78 } 79 int value = root->val; 80 Node* l = root->l; 81 Node* r = root->r; 82 Node* lBFS = posOrder(l, record); 83 int lSize = record[0]; 84 int lMin = record[1]; 85 int lMax = record[2]; 86 Node* rBFS = posOrder(r, record); 87 int rSize = record[0]; 88 int rMin = record[1]; 89 int rMax = record[2]; 90 record[1] = min(lMin, value); 91 record[2] = max(rMax, value); 92 if (l == lBFS && r == rBFS && lMax < value && value < rMin)//左边最大的小于右边最小的 93 { 94 record[0] = lSize + rSize + 1;//二叉树的大小 95 return root; 96 } 97 record[0] = max(lSize, rSize); 98 return lSize > rSize ? lBFS : rBFS; 99 }100 101 void solve02(Node* root)102 {103 int record[3] = { 0 };104 Node* res = posOrder(root, record);105 cout << record[0] << " " << res->val << endl;106 }107 108 int main()109 {110 Node* root = createTree();111 solve01(root);112 solve02(root);113 return 0; 114 }