用手机能创建网站吗,html5 珠宝网站,上海建站模板厂家,wordpress英文版修改栏执行结果#xff1a;通过 题目 1367 二叉树中的链表
给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
如果在二叉树中#xff0c;存在一条一直向下的路径#xff0c;且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值#xff0c;那么请你返回 …执行结果通过 题目 1367 二叉树中的链表
给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
如果在二叉树中存在一条一直向下的路径且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值那么请你返回 True 否则返回 False 。
一直向下的路径的意思是从树中某个节点开始一直连续向下的路径。 示例 1 输入head [4,2,8], root [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出true
解释树中蓝色的节点构成了与链表对应的子路径。示例 2 输入head [1,4,2,6], root [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出true示例 3
输入head [1,4,2,6,8], root [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出false
解释二叉树中不存在一一对应链表的路径。
提示
二叉树和链表中的每个节点的值都满足 1 node.val 100 。链表包含的节点数目在 1 到 100 之间。二叉树包含的节点数目在 1 到 2500 之间。、
代码以及解题思路
代码
bool dfs(struct TreeNode* rt, struct ListNode* head) {if (head NULL) {return true;}if (rt NULL) {return false;}if (rt-val ! head-val) {return false;}return dfs(rt-left, head-next) || dfs(rt-right, head-next);
}bool isSubPath(struct ListNode* head, struct TreeNode* root) {if (root NULL) {return false;}return dfs(root, head) || isSubPath(head, root-left) || isSubPath(head, root-right);}
解题思路
深度优先搜索DFS函数 dfs 参数接收一个二叉树的节点 rt 和一个链表的节点 head 作为参数。终止条件 如果链表已经遍历完head NULL说明当前路径匹配成功返回 true。如果二叉树节点为空rt NULL说明当前路径无法继续匹配返回 false。如果当前二叉树节点的值与链表节点的值不相等rt-val ! head-val说明当前路径不匹配返回 false。递归逻辑 如果当前节点匹配成功则尝试向左子树或右子树继续匹配链表的下一个节点即 dfs(rt-left, head-next) 或 dfs(rt-right, head-next)。使用逻辑或 || 是因为只要有一边匹配成功整个路径就匹配成功。主函数 isSubPath 参数接收链表的头节点 head 和二叉树的根节点 root 作为参数。终止条件 如果二叉树根节点为空root NULL说明无法继续搜索返回 false。递归逻辑 首先尝试从当前根节点开始匹配整个链表即 dfs(root, head)。如果从当前根节点开始匹配不成功则递归地对左子树和右子树调用 isSubPath 函数即 isSubPath(head, root-left) 或 isSubPath(head, root-right)。使用逻辑或 || 是因为只要有一边根节点开始、左子树或右子树能找到匹配的路径整个函数就返回 true。
总结
dfs 函数用于判断从二叉树的某个节点开始是否能匹配整个链表。isSubPath 函数用于递归地遍历二叉树的每个节点作为可能的路径起点调用 dfs 函数进行匹配。这两个函数共同实现了在二叉树中查找与给定链表完全相同的路径的功能。
