在树中查找子树
题目链接
leetcode 572
题意
给你两棵二叉树 root 和 subRoot
检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树
如果存在，返回 true ，否则，返回 false
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点
tree 也可以看做它自身的一棵子树
思路
递归遍历每个结点
拿到当前结点，递归判断以当前结点为根的子树是否与subRoot重合
class Solution {
public:bool isSubtree(TreeNode* root, TreeNode* subRoot) {if(root==nullptr)return subRoot==nullptr;if(issame(root,subRoot))return 1;return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);//找打一个匹配即可}bool issame(TreeNode*o,TreeNode*s){if(o==nullptr&&s==nullptr)return 1;if(o==nullptr||s==nullptr)return 0;if(o->val!=s->val)return 0;return issame(o->left,s->left)&&issame(o->right,s->right);//完全重合}
};
在树中查找链表
题目链接
leetcode 1367
题意
给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表
如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False
一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径
思路
递归遍历每个结点
拿到当前结点，递归判断链表能否插入当前子树
class Solution {
public:bool isSubPath(ListNode* head, TreeNode* root) {if(head==nullptr)return 1;if(root==nullptr)return 0;if(head->val==root->val&&dfs(head,root))return 1;return isSubPath(head,root->left)||isSubPath(head,root->right);}bool dfs(ListNode*h,TreeNode*o){if(h==nullptr)return 1;if(o==nullptr)return 0;if(h->val!=o->val)return 0;return dfs(h->next,o->left)||dfs(h->next,o->right);//能插入一个位置即可}
};