文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個二叉樹，找到其中最大的二叉搜索樹（BST）子樹，
其中最大指的是子樹節(jié)點數(shù)最多的。

注意:
子樹必須包含其所有后代。

示例: 輸入: [10,5,15,1,8,null,7]10 / \ 5 15 / \ \ 1 8 7 輸出: 3 解釋: 高亮部分為最大的 BST 子樹。（1，5，8）返回值 3 在這個樣例中為子樹大小。 進階: 你能想出用 O(n) 的時間復(fù)雜度解決這個問題嗎？

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/largest-bst-subtree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 自底向上dfs，返回值 子樹 min, max, node個數(shù), 是bst？

class Solution {int maxNode = 1; public:int largestBSTSubtree(TreeNode* root) {if(!root) return 0;dfs(root);return maxNode;}vector<int> dfs(TreeNode* root)//返回子樹min,max,node個數(shù),是bst？{ // 0 1 2 3if(!root) return {INT_MAX,INT_MIN,0,1};auto l = dfs(root->left);auto r = dfs(root->right);bool bst = (l[3] && r[3] && l[1] < root->val && root->val < r[0]);int node = l[2]+r[2]+1;int MAX = !root->right ? root->val : r[1],MIN = !root->left ? root->val : l[0];if(bst)maxNode = max(maxNode, node);return {MIN,MAX,node,bst};} };

20 ms 30.8 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 333. 最大 BST 子树（递归）*的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。