2021秋招-算法-递归

101. 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。1/ \2   2/ \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:1/ \2   2\   \3    3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def isMirror(self,t1,t2):if not t1 and not t2:return Trueif not t1 or not t2:return Falsereturn t1.val == t2.val and self.isMirror(t1.right,t2.left) and self.isMirror(t1.left,t2.right)def isSymmetric(self, root: TreeNode) -> bool:# 递归算法if not root:return Truereturn self.isMirror(root.left,root.right)'''# 非递归: BFS判断当前层元素是否为对称res = []if not root:return Truequeue = [root]row = 1while queue:line_res = []queue_size = len(queue)# 将当前队列元素向四周扩散for i in range(queue_size):curNode = queue.pop(0)# 划重点: 判断是否到达终止if curNode:line_res.append(curNode.val)queue.append(curNode.left)queue.append(curNode.right)else:line_res.append('null')# 判断当前层是否符合镜像二叉树要求if len(line_res) % 2 != 0 and row != 1: return Falseback = line_res[::-1]if line_res != back:return Falserow += 1 return True'''

剑指 Offer 24. 反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

• python 递归方法：
  

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def reverseList(self, head: ListNode) -> ListNode:if head == None or head.next == None:return head# 递归子链表# 下层递归返回值cur = self.reverseList(head.next)head.next.next = headhead.next = Nonereturn cur

• python迭代方法:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def reverseList(self, head: ListNode) -> ListNode:if not head:return None        pHead = headpTmp1 = head# 下面两条顺序不能变化,否则就会报错; pHead = pHead.nextpTmp1.next = Nonewhile pHead:# 原则: 两前1后指针pTmp2 = pHead.nextpHead.next = pTmp1pTmp1 = pHeadpHead = pTmp2return pTmp1

25. K 个一组翻转链表难度困难639收藏分享切换为英文关注反馈给你一个链表，
每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

思路: 使用 递归的思路:

python实现:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def reverseKGroup(self, head: ListNode, k: int) -> ListNode:# 翻转区间[a, b) 的元素, 注意是 左闭右开。  def reverse(a, b):pre = ListNode()cur = anxt = a# while终止条件变成 != bwhile cur != b:    nxt = cur.nextcur.next = prepre = curcur = nxt# 反转后的头节点return preif not head:return Nonea = b = headfor i in range(k):if not b:return headb = b.next# 返回z反转后的头节点newHead = reverse(a, b)# a: 反转之前的头节点, 然后把 反转后的 下一次的头节点拼起来a.next = self.reverseKGroup(b, k)return newHead