ChatGPT之程序代码复杂度计算¶

在产品开发过程中，除了保证产品功能外，我们往往希望产品具有好的时间复杂度和空间复杂度，这样能保证大规模用户使用过程中一直有良好的用户响应时间，即用户使用起来会非常流畅。另外，在码工面试过程中，考察程序代码的复杂度也是经常会问到的问题。这里，我们来体验一下用OpenAI ChatGPT来计算程序代码的复杂度。

对于编程题目，我们选取著名的Leetcode代码困难题。

从先序遍历还原二叉树¶

我们从二叉树的根节点root 开始进行深度优先搜索。在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为D，则其直接子节点的深度为 D + 1。根节点的深度为0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。给出遍历输出S，还原树并返回其根节点root。

链接：https://leetcode.cn/problems/recover-a-tree-from-preorder-traversal

整个体验过程如下。

我：我们来做一道编程题
Bot:好的，那么你有什么题目想做呢？

我：我们从二叉树的根节点 root 开始进行深度优先搜索。在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。如果节点只有一个子节点，那么保证该子节点为左子节点。给出遍历输出 S，还原树并返回其根节点 root。你想要我帮你设计算法还是提供代码实现呢？
Bot: 好的，那么我们可以用一个字符串数组来表示树的遍历结果，其中每个字符串由若干个短划线和一个节点值组成。我们可以用递归的方式还原树：

对于每一个字符串，如果它的第一个字符是短划线，那么就递归地还原它的左子节点；
如果第一个字符不是短划线，那么就把它转化为一个整数，创建一个新的节点，并设置它的值为该整数；
最后，如果字符串数组的下一个字符串的第一个字符是短划线，那么就递归地还原它的右子节点。

这样，我们就可以通过递归的方式还原一棵树了。以下是一个参考实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* recoverFromPreorder(string S) {
        int i = 0;
        return recoverFromPreorder(S, i, 0);
    }

private:
    TreeNode* recoverFromPreorder(const string& S, int& i, int depth) {
        int j = i;
        while (j < S.size() && S[j] == '-') {
            ++j;
        }
        int d = j - i;
        if (d != depth) {
            return nullptr;
        }
        i = j;
        while (i < S.
S.size() && isdigit(S[i])) { ++i; } int val = stoi(S.substr(j, i - j)); TreeNode* node = new TreeNode(val); node->left = recoverFromPreorder(S, i, depth + 1); node->right = recoverFromPreorder(S, i, depth + 1); return node; } };

上面的代码实现了递归函数 recoverFromPreorder，它的参数包括遍历输出的字符串 S、当前处理的字符串的索引 i 和当前节点的深度 depth。它会返回还原出的树的根节点。它的实现方式是： - 首先，使用一个循环读取短划线，并计算出当前节点的深度 d； - 然后，如果当前节点的深度 d 不等于参数 depth，那么就返回 nullptr； - 否则，使用一个循环读取数字，并转化为整数，创建一个新的节点，并设置它的值为该整数； - 接着，递归地还原该节点的左子节点； - 最后，如果字符串数组的下一个字符串的第一个字符是短划线，那么就递归地还原该节点的右子节点。这样，就可以通过递归的方式还原一棵树了。

我：这个算法时间复杂度分析一下
Bot: 这个算法的时间复杂度取决于遍历输出的字符串的长度。对于每一个字符串，我们都要对它进行一次读取操作，所以总的时间复杂度是线性的，即 \(O(n)\)，其中\(n\)是遍历输出的字符串的长度。空间复杂度方面，由于我们是使用递归的方式还原树，所以空间复杂度取决于树的深度。如果树的深度是 \(d\)，那么空间复杂度就是 \(O(d)\)。

最后欢迎一起讨论如何有效的利用AI帮助个人极大的提升工作效率。同时欢迎关注和收藏。（来源于：知乎，侵删）