增城营销型网站建设,怀化 优化生育政策,甘肃省住房和城乡建设部网站,网络营销做女鞋的网站设计1. 题目
给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。
如果在二叉树中#xff0c;存在一条一直向下的路径#xff0c;且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值#xff0c;那么请你返回 True #xff0c;否则返回 False 。
一直向…1. 题目
给你一棵以 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 之间。来源力扣LeetCode 链接https://leetcode-cn.com/problems/linked-list-in-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
遍历所有的节点节点与head值相等的再开启递归check是否存在链
class Solution {bool found false;
public:bool isSubPath(ListNode* head, TreeNode* root) {if(!root)return 0;if(found)return found;if(root-val head-val)check(root,head);isSubPath(head,root-left);isSubPath(head,root-right);return found;}void check(TreeNode* root, ListNode* head) {if((!root head) || found)return;if(!head){found true;return;}if(root-val head-val){check(root-left,head-next);check(root-right,head-next);}}
};
