LeetCode - Medium - 1367. Linked List in Binary Tree

叁歲伎倆 2022-10-11 03:36 116阅读 0赞

## Topic ##

*  Linked List
 *  Tree
 *  Depth-First Search
 *  Binary Tree

## Description ##

[https://leetcode.com/problems/linked-list-in-binary-tree/][https_leetcode.com_problems_linked-list-in-binary-tree]

Given a binary tree `root` and a linked list with `head` as the first node.

Return True if all the elements in the linked list starting from the `head` correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

**Example 1:**

![babe1c7df9f7da907011f12879b9c638.png][]

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
    Output: true
    Explanation: Nodes in blue form a subpath in the binary Tree.

**Example 2:**

![63ccaf938591109c38375f502dbf8994.png][]

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
    Output: true

**Example 3:**

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
    Output: false
    Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

**Constraints:**

*  The number of nodes in the tree will be in the range `[1, 2500]`.
 *  The number of nodes in the list will be in the range `[1, 100]`.
 *  `1 <= Node.val <= 100` for each node in the linked list and binary tree.

## Analysis ##

方法一：自己写的，DFS + 暴力算法。

方法二：自己写的，KMP + DFS。

方法三：别人写的，DFS + 暴力算法。

方法四：别人写的，KMP + DFS。

## Submission ##

import java.util.ArrayList;
    import java.util.List;
    
    import com.lun.util.BinaryTree.TreeNode;
    import com.lun.util.SinglyLinkedList.ListNode;
    
    public class LinkedListInBinaryTree { 
        
    	//方法一：自己写的，DFS + 暴力算法
    	public boolean isSubPath(ListNode head, TreeNode root) { 
        	if(root == null) return false;
            return helper(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
        }
        
    	private boolean helper(ListNode head, TreeNode root) { 
    		if(head != null && root == null)
    			return false;
    		
    		if(head != null && root != null) { 
    			if(head.val != root.val)
    				return false;
    			return helper(head.next, root.left) || helper(head.next, root.right);
    		}
    		return true;
    	}
    	
    	
    	//方法二：自己写的，KMP + DFS
    	public boolean isSubPath2(ListNode head, TreeNode root) { 
    		int[][] patternAndNext = getPatternAndNext(head);
    		return helper(patternAndNext, root, -1);
    	}
    	
    	private boolean helper(int[][] patternAndNext, TreeNode node, int j) { 
    		if(node == null) return false;
    
    		int[] pattern = patternAndNext[0], next = patternAndNext[1];
    		while(j >= 0 && node.val != pattern[j + 1])
    			j = next[j];
    		if(node.val == pattern[j + 1])
    			j++;
    		if(j == patternAndNext[0].length - 1)
    			return true;
    		
    		return helper(patternAndNext, node.left, j) || helper(patternAndNext, node.right, j);
    	}
    	
    	//KMP算法
    	private int[][] getPatternAndNext(ListNode head){ 
    		int count = 0;
    		ListNode p = head;
    		
    		while(p != null) { 
    			count++;
    			p = p.next;
    		}
    		
    		int[] pattern = new int[count]; 
    		p = head;
    		count = 0;
    		while(p != null) { 
    			pattern[count++] = p.val;
    			p = p.next;
    		}
    		
    		int[] next = new int[count];
    		
    		//正戏
    		int j = -1;
    		next[0] = j;
    		for(int i = 1; i < pattern.length; i++) { 
    			while(j >= 0 && pattern[i] != pattern[j + 1])
    				j = next[j];
    			if(pattern[i] == pattern[j + 1])
    				j++;
    			next[i] = j;
    		}
    		return new int[][] { pattern, next};
    	}
    	
    	//方法三：别人写的，DFS + 暴力算法
        public boolean isSubPath3(ListNode head, TreeNode root) { 
            if (head == null) return true;
            if (root == null) return false;
            return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
        }
    
        private boolean dfs(ListNode head, TreeNode root) { 
            if (head == null) return true;
            if (root == null) return false;
            return head.val == root.val && (dfs(head.next, root.left) || dfs(head.next, root.right));
        }
    	
        //方法四：别人写的，KMP + DFS
        public boolean isSubPath4(ListNode head, TreeNode root) { 
            List<Integer> A = new ArrayList<>(), dp = new ArrayList<>();
            A.add(head.val);
            dp.add(0);
            int i = 0;
            head = head.next;
            while (head != null) { 
                while (i > 0 && head.val != A.get(i))
                    i = dp.get(i - 1);
                if (head.val == A.get(i)) ++i;
                A.add(head.val);
                dp.add(i);
                head = head.next;
            }
            return dfs(root, 0, A, dp);
        }
    
        private boolean dfs(TreeNode root, int i, List<Integer> A, List<Integer> dp) { 
            if (root == null) return false;
            while (i > 0 && root.val != A.get(i))
                i = dp.get(i - 1);
            if (root.val == A.get(i)) ++i;
            return i == dp.size() || dfs(root.left, i, A, dp) || dfs(root.right, i, A, dp);
        }
    	
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    import com.lun.util.SinglyLinkedList;
    import com.lun.util.SinglyLinkedList.ListNode;
    
    public class LinkedListInBinaryTreeTest { 
    
        @Test
        public void test() { 
            LinkedListInBinaryTree lObj = new LinkedListInBinaryTree();
            
            TreeNode root1 = BinaryTree.of(1, 4, 4, null, 2, 2, null, 1, null, 6, 8, // 
            		null, null, null, null, 1, 3);
    
            ListNode head1 = SinglyLinkedList.of(4, 2, 8);
            assertTrue(lObj.isSubPath(head1, root1));
            
            ListNode head2 = SinglyLinkedList.of(1, 4, 2, 6);
            assertTrue(lObj.isSubPath(head2, root1));
            
            ListNode head3 = SinglyLinkedList.of(1, 4, 2, 6, 8);
            assertFalse(lObj.isSubPath(head3, root1));
        }
        
        @Test
        public void test2() { 
        	LinkedListInBinaryTree lObj = new LinkedListInBinaryTree();
        	
        	TreeNode root1 = BinaryTree.of(1, 4, 4, null, 2, 2, null, 1, null, 6, 8, // 
        			null, null, null, null, 1, 3);
        	
        	ListNode head1 = SinglyLinkedList.of(4, 2, 8);
        	assertTrue(lObj.isSubPath2(head1, root1));
        	
        	ListNode head2 = SinglyLinkedList.of(1, 4, 2, 6);
        	assertTrue(lObj.isSubPath2(head2, root1));
        	
        	ListNode head3 = SinglyLinkedList.of(1, 4, 2, 6, 8);
        	assertFalse(lObj.isSubPath2(head3, root1));
        }
        
        @Test
        public void test3() { 
        	LinkedListInBinaryTree lObj = new LinkedListInBinaryTree();
        	
        	TreeNode root1 = BinaryTree.of(1, 4, 4, null, 2, 2, null, 1, null, 6, 8, // 
        			null, null, null, null, 1, 3);
        	
        	ListNode head1 = SinglyLinkedList.of(4, 2, 8);
        	assertTrue(lObj.isSubPath3(head1, root1));
        	
        	ListNode head2 = SinglyLinkedList.of(1, 4, 2, 6);
        	assertTrue(lObj.isSubPath3(head2, root1));
        	
        	ListNode head3 = SinglyLinkedList.of(1, 4, 2, 6, 8);
        	assertFalse(lObj.isSubPath3(head3, root1));
        }
        
        @Test
        public void test4() { 
        	LinkedListInBinaryTree lObj = new LinkedListInBinaryTree();
        	
        	TreeNode root1 = BinaryTree.of(1, 4, 4, null, 2, 2, null, 1, null, 6, 8, // 
        			null, null, null, null, 1, 3);
        	
        	ListNode head1 = SinglyLinkedList.of(4, 2, 8);
        	assertTrue(lObj.isSubPath4(head1, root1));
        	
        	ListNode head2 = SinglyLinkedList.of(1, 4, 2, 6);
        	assertTrue(lObj.isSubPath4(head2, root1));
        	
        	ListNode head3 = SinglyLinkedList.of(1, 4, 2, 6, 8);
        	assertFalse(lObj.isSubPath4(head3, root1));
        }
        
    }

[https_leetcode.com_problems_linked-list-in-binary-tree]: https://leetcode.com/problems/linked-list-in-binary-tree/
[babe1c7df9f7da907011f12879b9c638.png]: /images/20221005/c84415f2b952465a8b201a8f052f891e.png
[63ccaf938591109c38375f502dbf8994.png]: /images/20221005/77844f54449a452fa226b66759704f2f.png