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

admin管理员组

文章数量:1029736

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

判断是不是平衡二叉树(递归)

• 判断是不是平衡二叉树

• 判断一个二叉树是不是平衡二叉树，我们需要知道其左子树和右子树是不是平衡二叉树，并且左右子树的高度差不超过1。
• 但是返回值只有一个，因此我们规定如果当前子树不是平衡二叉树，返回-1；如果是平衡二叉树则返回其高度。
• 整个过程是后序遍历。

代码语言：javascript代码运行次数：0运行复制

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

---

最大子矩阵(二维前缀和)

• 最大子矩阵

二维前缀和模板题。

代码语言：javascript代码运行次数：0运行复制

#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的个数相等时更新结果；
• 字符串成环，当从字符串中找到一段区间满足要求时，实际上找到了两个结果；
• 需要注意的是：当枚举到字符串边界时，其实另一边已经算过了，因此我们只能枚举一个边界。

代码语言：javascript代码运行次数：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;
}

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-19，如有侵权请联系 cloudcommunity@tencent 删除前往查看二叉树int遍历递归字符串

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

判断是不是平衡二叉树(递归)

• 判断是不是平衡二叉树

• 判断一个二叉树是不是平衡二叉树，我们需要知道其左子树和右子树是不是平衡二叉树，并且左右子树的高度差不超过1。
• 但是返回值只有一个，因此我们规定如果当前子树不是平衡二叉树，返回-1；如果是平衡二叉树则返回其高度。
• 整个过程是后序遍历。

代码语言：javascript代码运行次数：0运行复制

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

---

最大子矩阵(二维前缀和)

• 最大子矩阵

二维前缀和模板题。

代码语言：javascript代码运行次数：0运行复制

#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的个数相等时更新结果；
• 字符串成环，当从字符串中找到一段区间满足要求时，实际上找到了两个结果；
• 需要注意的是：当枚举到字符串边界时，其实另一边已经算过了，因此我们只能枚举一个边界。

代码语言：javascript代码运行次数：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;
}

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-19，如有侵权请联系 cloudcommunity@tencent 删除前往查看二叉树int遍历递归字符串

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