leetcode100.相同的树

题目

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

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

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

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

解答

解题思路：

题目要求判断两棵树是否完全相同。

我们可以使用递归的方法，递归判断两棵树的根节点是否相同，以及它们的左子树和右子树是否相同。

如果两棵树都为空，则返回 true。如果有一棵树为空，另一棵树不为空，则返回 false。如果两棵树的根节点的值不相等，则返回 false。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // 递归函数，判断两棵树是否相同
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 如果两棵树都为空，则返回 true
        if (!p && !q) return true;
        // 如果有一棵树为空，另一棵树不为空，则返回 false
        if (!p || !q) return false;
        // 如果两棵树的根节点的值不相等，则返回 false
        if (p->val != q->val) return false;
        // 递归判断两棵树的左子树和右子树是否相同
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

可以将代码简化为：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 如果两棵树都为空或者都不为空且值相等，则继续递归
        if (!p && !q) return true;
        if (p && q && p->val == q->val)
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        // 否则，返回 false
        return false;
    }
};