167.二叉树：另一棵树的字树（力扣）

代码解决

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 判断两棵树是否相同
    bool isSame(TreeNode* s, TreeNode* t) {
        if (s == nullptr && t == nullptr) {
            return true;  // 两棵树都为空，相同
        }
        if (s == nullptr || t == nullptr) {
            return false;  // 一棵树为空，一棵树非空，不相同
        }
        if (s->val != t->val) {
            return false;  // 根节点值不同，不相同
        }
        // 递归检查左右子树
        return isSame(s->left, t->left) && isSame(s->right, t->right);
    }
 
    // 判断 subRoot 是否是 root 的子树
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (root == nullptr) {
            return subRoot == nullptr;  // 如果 root 为空，subRoot 也必须为空才是子树
        }
        // 如果当前节点的子树和 subRoot 相同，返回 true
        if (isSame(root, subRoot)) {
            return true;
        }
        // 递归检查左子树和右子树
        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
};

解释：

1. isSame 函数：

   • isSame 函数用于判断两棵树 s 和 t 是否完全相同。
   • 如果两棵树都为空，则返回 true。
   • 如果一棵树为空而另一棵树非空，则返回 false。
   • 如果两棵树的根节点值不同，则返回 false。
   • 递归检查两棵树的左子树和右子树是否相同。

2. isSubtree 函数：

   • isSubtree 函数用于判断 subRoot 是否是 root 的子树。
   • 如果 root 为空，则只有当 subRoot 也为空时才返回 true。
   • 首先检查当前节点的子树是否和 subRoot 相同。
   • 如果不相同，递归检查 root 的左子树和右子树是否包含 subRoot。