免费论坛网站大全微信登陆wordpress
文章目录
- 1. 题目描述
- 2. 我的尝试
- 3. 其他题解
1. 题目描述
Leetcode 572 另一棵树的子树
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);}
};