当前位置：首页 > article >正文

【LeetCode刷题-树】--1367.二叉树中的链表

article 2024/9/25 11:19:42

1367.二叉树中的链表

方法：枚举

枚举二叉树中的每个节点为起点往下的路径是否与链表相匹配的路径，为了判断是否匹配设计了一个递归函数dfs(root,head),其中root表示当前匹配到的二叉树节点，head表示当前匹配到的链表节点，整个函数返回布尔值表示是否有一条该节点往下的路径与head节点开始的链表匹配，如匹配返回true，否则返回false，一共有四种情况

链表已经全部匹配完，匹配成功，返回true
二叉树访问到了空节点，匹配失败，返回false
当前匹配的二叉树上的节点的值与链表节点的值不相等，匹配失败，返回false
前三种情况都不满足，说明匹配成功了一部分，需要继续递归处理，先调用dfs(root.left,head.next)，如果返回结果是false，说明没有匹配的路径，需要继续在右子树中匹配，继续递归调用函数

接下来就是枚举，从根节点开始，如果当前匹配成功就直接返回true，否则继续找它的左儿子和右儿子是否满足

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubPath(ListNode head, TreeNode root) {
        if(root == null) return false;
        return dfs(head,root) || isSubPath(head,root.left) || isSubPath(head,root.right);
    }

    public boolean dfs(ListNode head,TreeNode root){
        //链表全部匹配完，匹配成功
        if(head == null) return true;
        //二叉树访问到了空节点，匹配失败
        if(root == null) return false;
        //当前匹配的二叉树上节点的值与链表节点的值不相等，匹配失败
        if(head.val != root.val) return false;
        return dfs(head.next,root.left) || dfs(head.next,root.right);

    }
}