LeetCode 剑指 Offer——合并两个排序的链表、树的子结构

合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

代码：

class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: cur = dum = ListNode(0) while l1 and l2: if l1.val < l2.val: cur.next, l1 = l1, l1.next else: cur.next, l2 = l2, l2.next cur = cur.next cur.next = l1 if l1 else l2 return dum.next

创建新链表，用两个指针分别遍历两链表表，边比较边添加到新链表。

时间复杂度O(M+N)，空间复杂度O(1)

树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如: 给定的树 A:

3 / \ 4 5 / \ 1 2

给定的树 B：

4 / 1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例1：

输入：A = [1,2,3], B = [3,1] 输出：false

示例2：

输入：A = [3,4,5,1,2], B = [4,1] 输出：true

代码：

class Solution: def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool: def recur(A, B): if not B: return True if not A or A.val != B.val: return False return recur(A.left, B.left) and recur(A.right, B.right) return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

递归判断，isSubStructure()函数判断B是否是A的子结构，recur判断B是否是根节点为A的A树子结构。

M,N分别为树A，B的节点数量，时间复杂度为O(M*N)，空间复杂度为O(N)。