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 = None

class Solution:
    def isMirror(self,t1,t2):
        if not t1 and not t2:
            return True
        if not t1 or not t2:
            return False
        return 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 True
        return self.isMirror(root.left,root.right)

        '''
        # 非递归: BFS判断当前层元素是否为对称
        res = []
        if not root:
            return True
        
        queue = [root]
        row = 1
        while 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 False
            back = line_res[::-1]
            if line_res != back:
                return False
            
            row += 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 = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        
        # 递归子链表
        # 下层递归返回值
        cur = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return cur

• python迭代方法:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        
        if not head:
            return None        
        
        pHead = head
        pTmp1 = head

		# 下面两条顺序不能变化,否则就会报错; 
        pHead = pHead.next
        pTmp1.next = None

        while pHead:
        	# 原则: 两前1后指针
            pTmp2 = pHead.next
            pHead.next = pTmp1
            pTmp1 = pHead
            pHead = pTmp2
        return 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 = None

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        # 翻转区间[a, b) 的元素, 注意是 左闭右开。  
        def reverse(a, b):
            pre = ListNode()
            cur = a
            nxt = a
            # while终止条件变成 != b
            while cur != b:    
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            
            # 反转后的头节点
            return pre

        if not head:
            return None
        
        a = b = head
        for i in range(k):
            
            if not b:
                return head
            b = b.next
        # 返回z反转后的头节点
        newHead = reverse(a, b)
        # a: 反转之前的头节点, 然后把 反转后的 下一次的头节点拼起来
        a.next = self.reverseKGroup(b, k)
        
        return newHead