Topic describes
You are given a binary tree with root and a linked list with head as the first node.
Return True if there is a path down in the binary tree and each point corresponds exactly to the value of each node in the list headed by head, otherwise return False.
A straight down path is a path that starts at a node in the tree and continues down.
Example 1:
Input: the head =,2,8 [4], root = [1,4,4, null, 2, 2, null, 1, null, 6, 8, null, null, null, null, 1, 3] output: true explanation: the blue of the node in the tree form the corresponding subpath and linked list. Example 2:
Input: the head =,4,2,6 [1], the root = [1,4,4, null, 2, 2, null, 1, null, 6, 8, null, null, null, null, 1, 3] output: true example 3:
Input: head =,4,2,6,8 [1], the root = [1,4,4, null, 2, 2, null, 1, null, 6, 8, null, null, null, null, 1, 3] output: false interpretation: there is no one-to-one correspondence in the binary tree list of paths.
Tip:
Each node in the binary tree and linked list has a value of 1 <= node.val <= 100. The list contains between 1 and 100 nodes. The number of nodes in a binary tree ranges from 1 to 2500.
Source: LeetCode Link: https://leetcode-cn.com/problems/linked-list-in-binary-tree Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
Their thinking
- Give priority to:
- Returns true when the list is empty, that is, the list has run out;
- Return false if the list is not finished and the tree node is finished;
- When the head val! = = root. Val; Return false;
- Otherwise, list nodes and tree nodes are equal;
- Start to judge the left subtree node and the current list node first; If not equal;
- Start judging the right subtree nodes of the tree and the nodes of the current list; So recursively;
code
/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val? : number, next? : ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val? : number, left? : TreeNode | null, right? : TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */
function isSubPath(head: ListNode | null, root: TreeNode | null) :boolean {
if(head==null) {return true;
}
if(root==null) {return false;
}
// Check whether the left and right child nodes are equal to the next list node;
return isSub(head,root)||isSubPath(head,root.left)||isSubPath(head,root.right);
};
function isSub(head: ListNode | null, node: TreeNode | null) :boolean{
if(head==null) {return true;
}
if(node==null) {return false;
}
if(head.val! ==node.val){return false;
}
// If the values are the same, continue to look at the left and right side of the satisfied
return isSub(head.next,node.left)||isSub(head.next,node.right)
}
Copy the code