二叉树中的重复子树时间和空间复杂度

Question

我在 GFG 上看到以下问题，查找二叉树中是否存在大小为 2 或更大的重复子树。

现在，它写在练习题要求中，到处都有文章说TC和空间复杂度都是O(N)，但我认为它是O(N^2)，因为这里的“子树”是一个

std::unordered_set

最坏情况下的大小为

N

，最坏情况下的每个元素都可以有大小

N

（并非所有元素都有大小

N

，但即使如此，空间也将是 O(N^2)）。另外，由于字符串连接是 O(N)，所以时间复杂度似乎也是 O(N^2)。

如果我们可以使用现代编译器或使用

std::vector<char>

在 O(1) 中进行串联，我可以以某种方式理解，但空间对我来说绝对看起来像 O(N^2) 。我这里理解有问题吗？

// C++ program to find if there is a duplicate
// sub-tree of size 2 or more.
#include <bits/stdc++.h>
using namespace std;

// Separator node
const char MARKER = '$';

// Structure for a binary tree node
struct Node {
    char key;
    Node *left, *right;
};

// A utility function to create a new node
Node* newNode(char key)
{
    Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return node;
}

unordered_set<string> subtrees;

// This function returns empty string if tree
// contains a duplicate subtree of size 2 or more.
string dupSubUtil(Node* root)
{
    string s = "";

    // If current node is NULL, return marker
    if (root == NULL)
        return s + MARKER;

    // If left subtree has a duplicate subtree.
    string lStr = dupSubUtil(root->left);
    if (lStr.compare(s) == 0)
        return s;

    // Do same for right subtree
    string rStr = dupSubUtil(root->right);
    if (rStr.compare(s) == 0)
        return s;

    // Serialize current subtree
    s = s + root->key + lStr + rStr;

    // If current subtree already exists in hash
    // table. [Note that size of a serialized tree
    // with single node is 3 as it has two marker
    // nodes.
    if (s.length() > 3
        && subtrees.find(s) != subtrees.end())
        return "";

    subtrees.insert(s);

    return s;
}

// Driver program to test above functions
int main()
{
    Node* root = newNode('A');
    root->left = newNode('B');
    root->right = newNode('C');
    root->left->left = newNode('D');
    root->left->right = newNode('E');
    root->right->right = newNode('B');
    root->right->right->right = newNode('E');
    root->right->right->left = newNode('D');

    string str = dupSubUtil(root);

    (str.compare("") == 0) ? cout << " Yes "
                           : cout << " No ";
    return 0;
}

Answer 1

你是对的：代码不是 O(n)。

它正在和你玩一个算法复杂的壳游戏。

---

那么它去哪儿了？

虽然代码在树上进行了明示 O(n) 传递，但这只是因为它使用哈希映射来作弊——通过将重新搜索转移到字符串比较中。

注意到底部附近的小

subtrees.find(s)

了吗？是的。这就是你缺少的 O(n·logn)。对于每个节点 O(n)，我们搜索所有其他找到的节点 O(logn+s(n)) 来查找匹配项。

但是等等，还有更多！

哈希映射不仅存储每个（唯一）节点树，它还存储每个完整集（唯一）子树！这会爆炸性地将信息复制到比原始树的 O(n) 空间要求更多！

^{⟶ 请记住 Big-O 会观察到最坏的情况。}

因此，对于每个节点，它都将完整的子树存储在哈希映射中。这也是 O(n·logn) 。

^{⟶ 如果对数据结构比较挑剔：可变长度字符串的空间要求不是恒定的。但即使在像本示例这样的小树和字符串大小优化的情况下，C++ 字符串类仍然比原始}

struct Node

大，使其处于 best Ω(1

---

观察结果

让我们看看作者做了什么。显然，这个想法是使用哈希映射将（键 ⟶ 节点）查找减少到 O(1)，但这与作者想象的一样遥远。

给出的示例树是

(A (B D E) (C () (B D E)))

。如果我们打印出

subtrees

哈希图，我们会得到：

  BD$$E$$
  E$$
  D$$

...看起来还不错（我们没有看到

E$$

在地图中重复两次），但我们应该已经在这里观察到了上述缺陷。请注意

E$$

和

D$$

在

BD$$E$$

中是如何重复的？

让我们将树更改为

(A (B D E) (C () (Q R S)))

（没有重复的子树）并运行算法并再次打印出

subtrees

哈希图：

  ABD$$E$$C$QS$$R$$
  R$$
  QS$$R$$
  S$$
  C$QS$$R$$
  BD$$E$$
  E$$
  D$$

哎呀！看来使用哈希映射在这里并没有真正的帮助。 （至少不是它的使用方式。）

^{⟶ 此输出的第 first 行将是 O(n)}

---

最终复杂度

时间和空间看起来都是 O(n·logn)。使用哈希图只会提高最佳情况下的空间复杂度（作者提供的。偷偷摸摸的不是吗？）。

^{⟶ 更好的太空场景是}

(A (A A A) (B () (A A A)))

。试试吧！

算法的设计与分析确实不是最容易掌握的事情。 （而且我不是大师。我在这里可能“完全”错了。如果我错了，我肯定会被其他比我更擅长这方面的人活活吃掉。）事实上，D＆A 是最困难的之一关于CS的事情。 （并且是值得多次学习的大学水平课程。）

在发布此消息之前我非常想坐在我的手上，因为我仍然有一种偷偷摸摸的感觉我错过了一些重要的事情，哈哈。