1、链表反转
2、反转二叉树
3、合并二叉树
4、对称二叉树
1、反转链表
反转链表
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre=None
while head:
tmp=head.next
head.next=pre
pre=head
head=tmp
return pre
备注反转字符串：
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
k=len(s)
if k==1:
return s
else :
l=k//2
for i in range(l):
tmp=s[i]
s[i]=s[k-i-1]
s[k-i-1]=tmp
return s
2、反转二叉树
反转二叉树在本身左右节点的替换上，以及+广度优先算法、层序遍历
（1）借助队列，保存每层的节点
（2）每层的节点都要遍历完，同时加入新的节点
BFS
2、反转二叉树，226. 翻转二叉树
（1）迭代的BFS /层序遍历
A\层序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return
d=[root]
while d:
for i in range(len(d)):
t=d.pop(0)
t.right,t.left=t.left,t.right
if t.left:
d.append(t.left)
if t.right:
d.append(t.right)
return root
B\宽度优先遍历
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return
d=[root]
while d:
t=d.pop(0)
t.right,t.left=t.left,t.right
if t.left:
d.append(t.left)
if t.right:
d.append(t.right)
return root
2、递归+反转
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return
root.right,root.left=root.left,root.right
if root.left:
self.invertTree(root.left)
if root.right:
self.invertTree(root.right)
return root
3、合并二叉树
（1）判断这个节点都有值，求和后修改节点的值
（2）判断这个节点不是都有值时，判断左节点是否为空，是则把右节点的值赋予左节点
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not (t1 and t2):
if not t1:
return t2
if not t2:
return t1
queue = [(t1,t2)]
while queue:
r1,r2 = queue.pop(0)
r1.val += r2.val
# 如果r1和r2的左子树都不为空，就放到队列中
# 如果r1的左子树为空，就把r2的左子树挂到r1的左子树上
if r1.left and r2.left:
queue.append((r1.left,r2.left))
elif not r1.left:
r1.left = r2.left
# 对于右子树也是一样的
if r1.right and r2.right:
queue.append((r1.right,r2.right))
elif not r1.right:
r1.right = r2.right
return t1
（2）递归写法
深度优先搜索
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
if not (t1 and t2):
if not t1:
return t2
if not t2:
return t1
merged = TreeNode(t1.val + t2.val)
merged.left = self.mergeTrees(t1.left, t2.left)
merged.right = self.mergeTrees(t1.right, t2.right)
4、对称的二叉树
（1）递归写法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:
return True
#判断左右节点是否对称
def bfs(left,right):
if not left and not right:
return True
elif not left or not right:
return False
elif left.val!=right.val:
return False
else:
return bfs(left.left,right.right) and bfs(left.right,right.left)
return bfs(root.left,root.right)
（2）迭代写法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:
return True
#判断左右节点是否对称，首先把根节点复制两遍加入队列
d=[(root,root)]
while d:
left,right=d.pop(0)
if not left and not right:
continue
elif not left or not right:
return False
elif left.val!=right.val:
return False
else:
d.append((left.left,right.right))
d.append((left.right,right.left))
return True
网友评论