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: leetcode-cn.com/problems/li… 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

A review of binary trees

【 Review old and learn new 】101. Symmetric binary treesUsing queue, recursive realization of binary tree judgment

【 Review old and learn new 】102. Sequence traversal of binary treesBreadth-first traversal, queue first in, first out principle

【 Review old and learn new 】104. Maximum depth of a binary treeBreadth-first traversal, recursive implementation