1. 题目描述
2. 我的尝试
以中序顺序从大树的根节点开始遍历,每次比较以当前节点为根节点的子树是否与小树相同。若某次比较结果为true
,说明小树是大树的子树。
比较两树是否相同时,只需先比较根节点是否相同,再递归地比较左右子树是否相同。
/**
* 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 isSubtree(TreeNode* root, TreeNode* subRoot) {
if (!root) return false;
if (cmp(root, subRoot)) return true;
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
bool cmp(TreeNode* a, TreeNode* b) {
if (!a || !b) return (!a && !b);
if (a->val != b->val) return false;
else return cmp(a->left, b->left) && cmp(a->right, b->right);
}
};