判断两个二叉树是否相等的算法

在计算机科学中，二叉树是一种常用的数据结构，由节点和连接它们的边组成。判断两个二叉树是否相等是一种基本的算法问题，解决这个问题有多种方法。本文将分别从递归算法、迭代算法和哈希表算法三个角度介绍判断两个二叉树是否相等的算法，并探讨它们的优缺点。

1. 递归算法

递归算法是最简单的判断两个二叉树是否相等的方法之一。首先，比较根节点是否相同，然后对比左右子树是否相等。当左右子树都相等时，二叉树就被认为是相等的。递归算法可以用如下的代码实现：

```

bool isSameTree(TreeNode* p, TreeNode* q) {

if (!p && !q) {

return true;

}

if (!p || !q) {

return false;

}

if (p->val != q->val) {

return false;

}

return isSameTree(p->left, q->left) && isSameTree(p->right, q->right)；

}

```

该算法的时间复杂度是O(n)，其中n是树中节点的数量。但是，递归算法可能会导致栈溢出，因此，如果二叉树的深度很大，递归算法可能不是一个理想的选择。

2. 迭代算法

迭代算法是一个更高效的判断两个二叉树是否相等的方法。该算法使用一个栈来存储待比较的节点，每个节点都按照顺序出栈。当出栈节点的值不相等时，代表两个二叉树不相等。如果出栈节点的值相等，则将它们的左右子树推入栈中继续比较。迭代算法可以用如下的代码实现：

```

bool isSameTree(TreeNode* p, TreeNode* q) {

stack > stk;

stk.push({p, q});

while (!stk.empty()) {

auto [t1, t2] = stk.top(); stk.pop();

if (!t1 && !t2) {

continue;

}

if (!t1 || !t2) {

return false;

}

if (t1->val != t2->val) {

return false;

}

stk.push({t1->left, t2->left});

stk.push({t1->right, t2->right});

}

return true;

}

```

迭代算法的时间复杂度是O(n)，空间复杂度也是O(n)，其中n为树中节点的数量。相比递归算法，迭代算法不会导致栈溢出，并且在平均情况下具有更好的性能。

3. 哈希表算法

哈希表算法是一种新的判断两个二叉树是否相等的算法。它可以将每个节点的值作为哈希表的键，并将左右子树作为哈希表的值。然后，使用哈希函数对每个节点进行哈希处理，最后比较两个哈希表是否相等。哈希表算法可以用如下的代码实现：

```

bool isSameTree(TreeNode* p, TreeNode* q) {

unordered_map > hash;

queue > q;

q.push({p, q});

while (!q.empty()) {

auto [t1, t2] = q.front(); q.pop();

if (!t1 && !t2) {

continue;

}

if (!t1 || !t2) {

return false;

}

if (t1->val != t2->val) {

return false;

}

if (hash.count(t1->val) && hash[t1->val] != make_pair(t1->left, t2->left)) {

return false;

}

if (hash.count(-t1->val) && hash[-t1->val] != make_pair(t1->right, t2->right)) {

return false;

}

hash[t1->val] = make_pair(t1->left, t2->left);

hash[-t1->val] = make_pair(t1->right, t2->right);

q.push({t1->left, t2->left});

q.push({t1->right, t2->right});

}

return true;

}

```

哈希表算法的时间复杂度是O(n），空间复杂度也是O(n)，其中n为树中节点的数量。哈希表算法的优点在于它可以处理任意数量的树，并且在大多数情况下具有比较高的性能。

综上所述，递归算法、迭代算法和哈希表算法都可以用于判断两个二叉树是否相等。它们各有优缺点，可以根据实际需求来选择合适的算法。