小鑫的算法之路：leetcode0100 相同的树

题目

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

提示：

• 两棵树上的节点数目都在范围 [0, 100] 内
• -104 <= Node.val <= 104

解法1：递归，深度优先搜索

两棵树如果相同，即两棵树的结构完全相同，同时节点具有相同的值。那么可以同时对两颗树采用前序遍历递归处理。

代码如下：

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if ((p == nullptr) && (q == nullptr)) {
            return true;
        }

        if ((p != nullptr) && (q != nullptr)) {
            if (p->val != q->val) {
                return false;
            }
            return (isSameTree(p->left, q->left) && isSameTree(p->right, q->right));
        }

        return false;
    }
};

时间复杂度为O(min(m, n))，m和n分别为两个二叉树的节点数，空间复杂度为O(min(m, n))，m和n分别为两个二叉树的节点数。执行结果如下：

解法2：迭代，广度优先搜索

本题也可通过迭代实现，可借助两个队列分别保存两棵二叉树已经访问的节点。代码如下：

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue left_buffer{};
        left_buffer.push(p);
        queue right_buffer{};
        right_buffer.push(q);
        while (!left_buffer.empty() && !right_buffer.empty()) {
            size_t count = left_buffer.size();
            if (count != right_buffer.size()) {
                return false;
            }
            for (size_t i = 0; i < count; ++i) {
                p = left_buffer.front();
                left_buffer.pop();
                q = right_buffer.front();
                right_buffer.pop();

                if ((p == nullptr) && (q == nullptr)) {
                    continue;
                }

                if ((p != nullptr) && (q != nullptr)) {
                    if (p->val != q->val) {
                        return false;
                    }
                    left_buffer.push(p->left);
                    left_buffer.push(p->right);
                    right_buffer.push(q->left);
                    right_buffer.push(q->right);
                    continue;
                }

                return false;
            }
        }

        return true;
    }
};

时间复杂度为O(min(m, n))，m和n分别为两个二叉树的节点数，空间复杂度为O(min(m, n))，m和n分别为两个二叉树的节点数。执行结果如下：

解法3：迭代，广度优先搜索

在解法2中，通过两个队列分别保存左右两棵二叉树已经访问的节点。此时，也可通过一个队列来保存，只是在保存的时候需要同时保存两颗树的节点，同时在d出节点的时候也需要连续获取两个。代码如下：

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue buffer{};
        buffer.push(p);
        buffer.push(q);
        while (!buffer.empty()) {
            p = buffer.front();
            buffer.pop();
            q = buffer.front();
            buffer.pop();

            if ((p == nullptr) && (q == nullptr)) {
                    continue;
                }

            if ((p != nullptr) && (q != nullptr)) {
                if (p->val != q->val) {
                    return false;
                }
                buffer.push(p->left);
                buffer.push(q->left);
                buffer.push(p->right);
                buffer.push(q->right);
                continue;
            }

            return false;
        }

        return true;
    }
};

时间复杂度为O(min(m, n))，m和n分别为两个二叉树的节点数，空间复杂度为O(min(m, n))，m和n分别为两个二叉树的节点数。执行结果如下：