Medium

题目描述

给你一棵以 root 为根的二叉树和一个由 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下走直到走到树的某个节点（没有必要非要走到叶节点）。

示例 1：

输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true
解释：树中蓝色的节点构成了与链表对应的子路径。

示例 2：

输入：head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true

示例 3：

输入：head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：false
解释：二叉树中不存在一条一直向下的路径来包含链表中所有节点。

提示：

  • 二叉树中节点的数目范围是 [1, 2500]
  • 链表中节点的数目范围是 [1, 100]
  • 1 <= Node.val <= 100 链表和二叉树中的每个节点的值都满足此条件

解题思路

这是一个典型的双重递归问题，需要两个递归函数配合解决：

核心思路：

  1. 主递归函数 isSubPath：遍历二叉树的每个节点，尝试以该节点为起点匹配链表
  2. 辅助递归函数 dfs：从当前树节点开始，检查是否能完全匹配剩余的链表

具体步骤：

  • 对于二叉树的每个节点，都尝试以该节点为起点进行链表匹配
  • 如果当前节点匹配成功，继续递归检查左右子树
  • 在匹配过程中，如果链表已经完全匹配完（head为null），返回true
  • 如果树节点为空但链表还有剩余，返回false
  • 如果当前节点值不匹配，返回false，但主函数会继续尝试其他节点

优化要点：

  • 一旦找到完整匹配就可以返回true
  • 利用短路求值，避免不必要的递归调用

时间复杂度：O(N×min(L,H))，其中N是树节点数，L是链表长度，H是树高度。空间复杂度：O(H)，递归栈的深度。

代码实现

class Solution {
public:
    bool isSubPath(ListNode* head, TreeNode* root) {
        if (!root) return false;
        return dfs(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
    }
    
private:
    bool dfs(ListNode* head, TreeNode* root) {
        if (!head) return true;
        if (!root) return false;
        return head->val == root->val && (dfs(head->next, root->left) || dfs(head->next, root->right));
    }
};

class Solution:
    def isSubPath(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        if not root:
            return False
        return self.dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
    
    def dfs(self, head: Optional[ListNode], root: Optional[TreeNode]) -> bool:
        if not head:
            return True
        if not root:
            return False
        return head.val == root.val and (self.dfs(head.next, root.left) or self.dfs(head.next, root.right))

public class Solution {
    public bool IsSubPath(ListNode head, TreeNode root) {
        if (root == null) return false;
        return Dfs(head, root) || IsSubPath(head, root.left) || IsSubPath(head, root.right);
    }
    
    private bool 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));
    }
}

var isSubPath = function(head, root) {
    if (!head) return true;
    if (!root) return false;
    
    return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
};

function dfs(head, root) {
    if (!head) return true;
    if (!root) return false;
    
    if (head.val !== root.val) return false;
    
    return dfs(head.next, root.left) || dfs(head.next, root.right);
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(N × min(L,H))N为树节点数，L为链表长度，H为树高度，最坏情况下需要对每个树节点都进行完整的链表匹配
空间复杂度O(H)递归调用栈的最大深度为树的高度