我发现在这个系列不给每日的主题了。

110. Balanced Binary Tree

Analysis

判断一颗树是否是平衡二叉树。

Code

bfs

用 dfs 写了半天还是 WA 了，改用 bfs 了😤。
bfs：

class Solution {
public:
    int getdepth(TreeNode *root) {
        if(!root) return 0;
        return max(getdepth(root->left), getdepth(root->right)) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode *node = q.front(); q.pop();
            if(abs(getdepth(node->left) - getdepth(node->right)) > 1) return false;
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
        return true;
    }
};

用 bfs 感觉思考起来轻松很多啊。

dfs

em，用 bfs 通过之后，思路清晰了很多，又把 dfs 改了一下通过了。
dfs：

class Solution {
public:
    int getdepth(TreeNode *root) {
        if(!root) return 0;
        return max(getdepth(root->left), getdepth(root->right)) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        if(!root->left) return getdepth(root->right) <= 1;
        if(!root->right) return getdepth(root->left) <= 1;
        return abs(getdepth(root->left) - getdepth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};

改一下：

class Solution {
public:
    int getdepth(TreeNode *root) {
        if(!root) return 0;
        return max(getdepth(root->left), getdepth(root->right)) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        if(!root->left) return getdepth(root->right) <= 1;
        if(!root->right) return getdepth(root->left) <= 1;
        if(abs(getdepth(root->left) - getdepth(root->right)) > 1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
    }
};

感觉思路还是不够清晰，再改下：

class Solution {
public:
    int getdepth(TreeNode *root) {
        if(!root) return 0;
        return max(getdepth(root->left), getdepth(root->right)) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        if(!root->left) return getdepth(root->right) <= 1 && isBalanced(root->right);
        if(!root->right) return getdepth(root->left) <= 1 && isBalanced(root->left);
        if(abs(getdepth(root->left) - getdepth(root->right)) > 1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
    }
};

试了下，也可以不写这么多 if（XD）：

class Solution {
public:
    int getdepth(TreeNode *root) {
        if(!root) return 0;
        return max(getdepth(root->left), getdepth(root->right)) + 1;
    }
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        return abs(getdepth(root->left) - getdepth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
};

以上代码的思路实际上是基于先序遍历的思路来完成的，这种思路的缺点在于每遇到一个结点就要计算出其子树的深度，在计算深度的过程中，就会重复的遍历那些叶子结点。为了避免这个缺点，可以使用后序遍历的思路来完成：

class Solution {
public:
    int height(TreeNode *root) {
        if(!root) return 0;
        int leftheight = height(root->left);
        int rightheight = height(root->right);
        if(leftheight == -1 || rightheight == -1 || abs(leftheight - rightheight) > 1) return -1;
        else return max(leftheight, rightheight) + 1;
    }
    bool isBalanced(TreeNode* root) {
        return height(root) >= 0;
    }
};

两种思考方法其实大同小异。

459. Repeated Substring Pattern

Analysis

判断一个字符串是否可以由其子串重复构成。

Code

method 1

先暴力做一下：

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int len = s.length();
        for(int i = 1; i <= len / 2; i++) {
            if(len % i == 0) {
                for(int j = 0; j < len - i; j += i) {
                    string tmp = s.substr(j, i), t;
                    while(t.length() < len) t += tmp;
                    if(t == s) return true;
                }
            }
        }
        return false;
    }
};

果然超时了。观察一下上面的暴力解法，在第二层循环内，按间隔去除子串后，又按照原字符串的长度，将子串构造成等长的字符串，最后再判断是否一致，从而来判断是否满足条件，所以这段代码的时间复杂度是 $O(n^3)$。
可问题在于，真的需要重新构造一个字符串，来进行判断吗？
答案是不用，因为每次枚举的是子串的长度，所以只需要根据这个长度来判断不同子串的字符是否一致即可。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int len = s.length();
        for(int i = 1; i <= len / 2; i++) {
            if(len % i == 0) {
                for(int j = 0; j < len - i; j += i) {
                    string tmp = s.substr(j, i), t;
                    while(t.length() < len) t += tmp;
                    if(t == s) return true;
                }
            }
        }
        return false;
    }
};

这段代码的时间复杂度是 $O(n^2)$，是可以通过的。

method 2

有了上面的思考，应该就认识到这个题是个字符串匹配的问题，毫无疑问，可以用 KMP 来完成。但 KMP 早就忘了，以后再看吧。
仔细观察一下样例，符合条件的字符串都有一个特点，那就是其满足条件的子串一定是出现多次的（实际上最少得出现 2 次，此时子串的长度是原串的一半）。这样，不妨原串 s 拼接成 s+s，然后第一个字符与最后一个字符，得到一个新字符串 news，此时再来判断 s 是否是 news 的子串。如果是，那么就是满足条件的，反之则不满足条件。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        return (s + s).find(s, 1) != s.length();
    }
};

直接调用库函数就可以完成，也不用严格意义上的删除第一个字符与最后一个字符。

Summary

虽然是 2 个简单题，不过都得动动脑子才能通过啊。如果还想要更优的解法，还得下更多功夫...
另外，至于 KMP，日后再说了...😑