C++判断两棵树是否为相同的树

**判断两棵树是否为相同的树**

在计算机科学中，树是一种常见的数据结构，它由结点组成，每个结点都有零个或多个子结点。判断两棵树是否为相同的树是一个重要的问题，这涉及到比较两个树的结构和内容。

**定义**

我们可以将一个树定义为以下结构：

cppstruct TreeNode {
 int val;
 TreeNode *left;
 TreeNode *right;
};

cppbool isSameTree(TreeNode *p, TreeNode *q) {
 // 如果两个树都为空，返回 true if (p == nullptr && q == nullptr)
 return true;
 // 如果一个树为空，而另一个树不为空，返回 false if (p == nullptr || q == nullptr)
 return false;
 // 如果两个树的值相同，则继续比较左子树和右子树 if (p->val == q->val) {
 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
 }
 // 如果两个树的值不同，返回 false return false;
}

cppbool isSameTree(TreeNode *p, TreeNode *q) {
 if (p == nullptr && q == nullptr)
 return true;
 if (p == nullptr || q == nullptr)
 return false;
 std::queue queue1, queue2;
 queue1.push(p);
 queue2.push(q);
 while (!queue1.empty()) {
 TreeNode *node1 = queue1.front();
 TreeNode *node2 = queue2.front();
 if (node1->val != node2->val)
 return false;
 queue1.pop();
 queue2.pop();
 if (node1->left && node2->left) {
 queue1.push(node1->left);
 queue2.push(node2->left);
 } else if (node1->left || node2->left) {
 return false;
 }
 if (node1->right && node2->right) {
 queue1.push(node1->right);
 queue2.push(node2->right);
 } else if (node1->right || node2->right) {
 return false;
 }
 }
 return true;
}