leetcode5346. 二叉树中的列表
给你一棵以 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
解释：树中蓝色的节点构成了与链表对应的子路径。
第一次打周赛，死的很惨，看了一下评论区的解法，我改进了一下我当时的提交。开始我想写一个方法，既能遍历所有的节点，又能查找子串，但是发现这么写难度很大，而且好不容易改好一个提交还超时。
对于最后一组样例，我觉得可能跟这个类似：
1
2
| [2,2,1]
[1,1,2,null,null,null,2,2,2,1,2,1,2]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public boolean flag=false;
public boolean isSubPath(ListNode head, TreeNode root) {
if(root==null)return false;
if(head==null)return false;
flag=false;
tt(root,head);
return flag;
}
public void tt(TreeNode root,ListNode head){
if(root==null)return;
if(!flag){
traverse(root,head);
if(flag==false){
tt(root.left,head);
tt(root.right,head);
}
}
}
public void traverse(TreeNode root,ListNode head){
if(head==null){
flag=true;
return;
}
if(root==null)return;
if(root.val==head.val){
traverse(root.left,head.next);
traverse(root.right,head.next);
}
}
}
|
leetcode 43/100