【Leetcode 每日一题】1367. 二叉树中的链表

问题背景

给你一棵以 $root$ 为根的二叉树和一个 $head$ 为第一个节点的链表。
如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 $head$ 为首的链表中每个节点的值，那么请你返回 $True$，否则返回 $False$。
一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

数据约束

• 二叉树和链表中的每个节点的值都满足$1\le node.val\le 100$
• 链表包含的节点数目在 $1$ 到 $100$ 之间
• 二叉树包含的节点数目在 $1$ 到 $2500$ 之间

解题过程

链表可以看作退化的二叉树，参考 检查子树，找链表和找子树是很类似的。
区别在于，链表不要求和树结构完全一致，所以递归过程中部分逻辑细节要修改一下。

具体实现

/**
 * 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) {
        // 底下要用对 root 的对象进行引用，必须特判它为空的情形
        // 待查找的树已经为空，无法进一步匹配，结果应该是 false
        if(root == null) {
            return false;
        }
        // 当前节点上可能找到链表的情况下，递归判断左右子树
        return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
    }

    private boolean dfs(ListNode head, TreeNode root) {
        // 链表已经遍历完毕，说明找到了这样的结构，返回 true
        if(head == null) {
            return true;
        }
        // 链表尚未遍历完毕，树已经空了或者当前节点的值不相等，不用继续往下递归了
        if(root == null || head.val != root.val) {
            return false;
        }
        // 递归到左右子树上，进一步判断是否符合条件
        return dfs(head.next, root.left) || dfs(head.next, root.right);
    }
}