题目
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2] 输出：true
示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] 输出：false
提示：
- root 树上的节点数量范围是 [1, 2000]
- subRoot 树上的节点数量范围是 [1, 1000]
- − 1 0 4 -10^4−104 <= root.val <= 1 0 4 10^4104
- − 1 0 4 -10^4−104 <= subRoot.val <= 1 0 4 10^4104
解题
方法一：迭代
层次遍历+对每个节点判断是否是相同的树
判断相同的树，和leetcode-100：相同的树一模一样。
python解法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool: queue = collections.deque([root]) while queue: cur = queue.popleft() left,right = cur.left,cur.right if cur.val==subRoot.val and self.compare(cur,subRoot): return True if left: queue.append(left) if right: queue.append(right) return False def compare(self,p,q): if not (p or q): return True if not (p and q): return False queue_q = collections.deque([q]) queue_p = collections.deque([p]) while queue_q and queue_p: cur_p = queue_p.popleft() cur_q = queue_q.popleft() if not (cur_p or cur_q): continue if not cur_p or not cur_q or cur_p.val!=cur_q.val: return False queue_p.append(cur_p.left) queue_q.append(cur_q.left) queue_p.append(cur_p.right) queue_q.append(cur_q.right) return True
c++解法
class Solution { public: bool compare(TreeNode* p,TreeNode* q){ if(!(p||q)) return true; if(!(p&&q)) return false; queue<TreeNode*> queue_p; queue<TreeNode*> queue_q; queue_p.push(p); queue_q.push(q); while(!queue_p.empty()&&!queue_q.empty()){ TreeNode* cur_p=queue_p.front(); queue_p.pop(); TreeNode* cur_q=queue_q.front(); queue_q.pop(); if(!(cur_p||cur_q)) continue; if(!cur_p||!cur_q||cur_p->val!=cur_q->val) return false; queue_p.push(cur_p->left); queue_p.push(cur_p->right); queue_q.push(cur_q->left); queue_q.push(cur_q->right); } return true; } bool isSubtree(TreeNode* root, TreeNode* subRoot) { queue<TreeNode*> queue; queue.push(root); while(!queue.empty()){ TreeNode* cur=queue.front(); queue.pop(); if(cur->val==subRoot->val&&compare(cur,subRoot)){ return true; } if(cur->left) queue.push(cur->left); if(cur->right) queue.push(cur->right); } return false; } };
方法二：递归
class Solution { public: //isSame这个函数和 100题.相同的树 一样的写法 bool isSame(TreeNode* p,TreeNode* q){ if(!(p||q)) return true; if(!(p&&q)) return false; if(p->val!=q->val) return false; return isSame(p->left,q->left)&&isSame(p->right,q->right); } //前序遍历二叉树root，查找是否有子树subRoot bool isSubtree(TreeNode* root, TreeNode* subRoot) { if(!subRoot) return true; if(!root) return false; //如果节点和子树根节点相等，那么就检查 子树是相同 bool check=false; if(root->val==subRoot->val){ check=isSame(root,subRoot); } //检查 当前节点作为子树、左子树、右子树 return check||isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot); } };
