代码解决
/** * 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); } };
解释:
isSame 函数:
isSame
函数用于判断两棵树s
和t
是否完全相同。- 如果两棵树都为空,则返回
true
。- 如果一棵树为空而另一棵树非空,则返回
false
。- 如果两棵树的根节点值不同,则返回
false
。- 递归检查两棵树的左子树和右子树是否相同。
isSubtree 函数:
isSubtree
函数用于判断subRoot
是否是root
的子树。- 如果
root
为空,则只有当subRoot
也为空时才返回true
。- 首先检查当前节点的子树是否和
subRoot
相同。- 如果不相同,递归检查
root
的左子树和右子树是否包含subRoot
。