【LeetCode热题100】打卡第40天：翻转二叉树&回文链表

**翻转二叉树 & 回文链表**

### 一、翻转二叉树####1. 题目描述给定一个二叉树的根节点，返回翻转这棵二叉树的根节点。

示例：

输入：[4,7,9,3,6,8,5]

输出：[4,7,9,3,6,8,5] -> [4,3,9,6,8,7,5]

####2. 思路翻转二叉树的思路是，先将左子树和右子树交换，然后递归地对左右子树进行翻转。

####3.代码实现

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef invertTree(root):
 """
 :type root: TreeNode :rtype: TreeNode """
 # 如果根节点为空，则直接返回None if not root:
 return None # 交换左右子树 root.left, root.right = root.right, root.left # 递归地对左右子树进行翻转 invertTree(root.left)
 invertTree(root.right)
 return root# 测试代码root = TreeNode(4)
root.left = TreeNode(7)
root.right = TreeNode(9)
root.left.left = TreeNode(3)
root.left.right = TreeNode(6)
root.right.left = TreeNode(8)
root.right.right = TreeNode(5)

print("原树：")
def printTree(root):
 if not root:
 return print(root.val, end=" ")
 printTree(root.left)
 printTree(root.right)
printTree(root) # 输出:4793685new_root = invertTree(root)

print("
翻转树：")
printTree(new_root) # 输出:4396875

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef isPalindrome(head):
 """
 :type head: ListNode :rtype: bool """
 # 将链表转换为列表 nums = []
 while head:
 nums.append(head.val)
 head = head.next # 比较列表是否为回文 return nums == nums[::-1]

# 测试代码head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(2)
head.next.next.next.next = ListNode(1)

print(isPalindrome(head)) # 输出:Truehead = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

print(isPalindrome(head)) # 输出:False