572. 另一棵树的子树-爱代码爱编程
572. 另一棵树的子树
题目
传送门:https://leetcode.cn/problems/subtree-of-another-tree/
算法设计:深度优先搜索
遍历以 root 为根的这棵二叉树的所有节点,判断以该节点为根的子树是否和以 subRoot 为根的那棵树相同。
class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if(!s) return false;
if (isSame(s,t)) return true; // 枚举父节点和TA下面的孩子节点能否产生相同的结构
return isSubtree(s->left, t) || isSubtree(s->right, t);
// 去左右子树中判断是否有和 subRoot 相同的子树
}
bool isSame(TreeNode *s, TreeNode *t) { // 判断俩个节点是否相同
if (!s && !t) return true;
if (!s || !t) return false;
if (s->val != t->val) return false;
return isSame(s->left, t->left) && isSame(s->right, t->right);
// 判断其他节点是否相同
}
};