【今日三题】判断是不是平衡二叉树(递归) / 最大子矩阵(二维前缀和) / 小葱的01串(滑动窗口)

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;
}

#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;
}