C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)

下面是 C++ 基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)的详细攻略：

问题分析

题目要求我们判断两个二叉树的结构和数据是否完全相同。这里所说的“结构相同”指的是两棵树的节点数、节点的左右子树结构相同，而“数据相同”指的是两棵树的节点存储的数据值相等。

递归算法实现

递归是二叉树算法中最经典的算法之一，而判断两个二叉树结构是否相同，也可以通过递归算法实现。递归的思路是：先判断两棵树的根节点是否相等，再递归判断它们的左右子树是否相等。

具体地，我们可以使用以下的递归函数实现：

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == nullptr && q == nullptr) {
        // 如果两个节点都是空节点，说明结构和数据都相同
        return true;
    } else if (p == nullptr || q == nullptr) {
        // 如果其中一个节点是空节点，说明结构不同
        return false;
    } else if (p->val != q->val) {
        // 如果两个节点的数据值不相等，说明数据不同
        return false;
    } else {
        // 递归判断左右子树是否相同
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
}

在函数中，首先判断两个节点是否都是空节点，如果是，说明结构和数据都相同，返回 true。如果其中一个节点是空节点，另一个不是，说明结构不同，返回 false。然后判断两个节点的数据值是否相等，如果不相等，说明数据不同，返回 false。最后，递归判断两个节点的左右子树是否相同。

非递归算法实现

递归算法虽然简单易懂，但是它有一个缺点，就是如果树的深度过大，递归调用会导致栈溢出。因此，我们还可以使用非递归算法实现题目要求。

具体地，我们可以借助栈的帮助，将两棵二叉树的节点依次放入栈中，然后依次比较它们的数据值。如果数据值不相等，说明两棵树结构和数据不同，返回 false；否则，继续比较它们的左右子树。

以下是非递归算法的实现代码：

bool isSameTree(TreeNode* p, TreeNode* q) {
    stack<TreeNode*> stk;
    stk.push(p);
    stk.push(q);

    while (!stk.empty()) {
        TreeNode* node1 = stk.top(); stk.pop();
        TreeNode* node2 = stk.top(); stk.pop();

        if (node1 == nullptr && node2 == nullptr) {
            // 如果两个节点都是空节点，说明结构和数据都相同
            continue;
        } else if (node1 == nullptr || node2 == nullptr) {
            // 如果其中一个节点是空节点，说明结构不同
            return false;
        } else if (node1->val != node2->val) {
            // 如果两个节点的数据值不相等，说明数据不同
            return false;
        } else {
            // 将左右子节点依次入栈
            stk.push(node1->left);
            stk.push(node2->left);
            stk.push(node1->right);
            stk.push(node2->right);
        }
    }
    return true;
}

与递归算法相比，非递归算法使用了一个栈来存储节点，然后依次比较它们的数据值。如果两个节点的数据值不相等，说明两棵树结构和数据不同，返回 false；否则，将它们的左右子节点依次入栈，继续比较。

示例说明

假设有以下两棵二叉树：

1               1

/ \ / \
2 3 2 3

它们都是如上图所示的二叉树。由于它们的结构和数据都相同，因此，无论是递归算法还是非递归算法，都会返回 true。

再假设有以下两棵二叉树：

1               1

/ \ / \
2 3 2 4

这两棵树的结构相同，但是数据不同。因此，递归算法和非递归算法都会返回 false。