LeetCode 1367. 二叉树中的链表

题目描述

✅ 1367. 二叉树中的链表

image-20250416231404738

image-20250416231444300

思路分析

  1. 首先，我们需要定义一个递归函数来遍历二叉树。
  2. 在遍历过程中，我们需要检查当前节点的值是否与链表的当前节点值相等。
  3. 如果相等，则继续检查下一个链表节点和当前节点的左右子树。
  4. 如果链表遍历完且当前节点是叶子节点，则返回 true。
  5. 如果不相等或链表遍历完但当前节点不是叶子节点，则返回 false。

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20



func isSubPath(head *ListNode, root *TreeNode) bool {
	var dfs func(node *TreeNode, curr *ListNode) bool
	dfs = func(node *TreeNode, curr *ListNode) bool {
		if curr == nil {
			return true // 链表遍历完，返回 true
		}
		if node == nil || node.Val != curr.Val {
			return false // 当前节点为空或值不匹配，返回 false
		}
		// 继续遍历左右子树
		return dfs(node.Left, curr.Next) || dfs(node.Right, curr.Next)
	}

	// 从根节点开始遍历
	if root == nil {
		return false
	}
	return dfs(root, head) || isSubPath(head, root.Left) || isSubPath(head, root.Right)
}
  • 时间复杂度：O (m * n)，其中 m 是链表的长度，n 是二叉树的节点数。最坏情况下，我们需要遍历每个节点并检查链表。
  • 空间复杂度：O (h)，其中 h 是二叉树的高度，递归调用栈的空间复杂度。

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2025/55134376
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！