??個人主頁：@小羊 ??所屬專欄：每日兩三題 很榮幸您能閱讀我的文章，誠請評論指點，歡迎歡迎 ~

---

判斷是不是平衡二叉樹(遞歸)

• 判斷是不是平衡二叉樹

• 判斷一個二叉樹是不是平衡二叉樹，我們需要知道其左子樹和右子樹是不是平衡二叉樹，并且左右子樹的高度差不超過1。
• 但是返回值只有一個，因此我們規定如果當前子樹不是平衡二叉樹，返回-1；如果是平衡二叉樹則返回其高度。
• 整個過程是后序遍歷。

class Solution {
public:bool IsBalanced_Solution(TreeNode* pRoot) {return dfs(pRoot) != -1;}int dfs(TreeNode* root){if (root == nullptr) return 0;int left = dfs(root->left);if (left == -1) return -1; // 剪枝int right = dfs(root->right);if (right == -1) return -1;return abs(right - left) <= 1 ? max(left, right) + 1 : -1;}
};

---

最大子矩陣(二維前綴和)

• 最大子矩陣

二維前綴和模板題。

#include <iostream>
using namespace std;int pre[101][101];
int n, res = -0x3f3f3f3f;int main()
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){int x;cin >> x;pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + x;}}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){for (int k = i; k <= n; k++){for (int l = j; l <= n; l++){res = max(res, pre[k][l] - pre[i - 1][l] - pre[k][j - 1] + pre[i - 1][j - 1]);}}}}cout << res << endl;return 0;
}

---

小蔥的01串(滑動窗口)

• 小蔥的01串

• 也就是在字符串上維護一段長度為n/2的窗口，當窗口內的0和1的個數和外面0和1的個數相等時更新結果；
• 字符串成環，當從字符串中找到一段區間滿足要求時，實際上找到了兩個結果；
• 需要注意的是：當枚舉到字符串邊界時，其實另一邊已經算過了，因此我們只能枚舉一個邊界。

#include <iostream>
#include <string>
using namespace std;int n, res;
string s;int main()
{cin >> n >> s;int x = 0, y = 0;for (auto ch : s){if (ch == '0') x++;else y++;}if (x % 2) res = 0;else{x /= 2, y /= 2;for (int l = 0, r = 0; r < n - 1; r++){if (s[r] == '0') x--;else y--;while (r - l + 1 > n / 2){if (s[l++] == '0') x++;else y++;}if (r - l + 1 == n / 2){if (x == 0 && y == 0){res++;}}}}cout << res * 2 << endl;return 0;
}

---

本篇文章的分享就到這里了，如果您覺得在本文有所收獲，還請留下您的三連支持哦~