代码随想录27期|Python|Day15|二叉树|层序遍历|对称二叉树|翻转二叉树

本文图片来源：代码随想录

层序遍历（图论中的广度优先遍历）

这一部分有10道题，全部可以套用相同的层序遍历方法，但是需要在每一层进行处理或者修改。

102. 二叉树的层序遍历 - 力扣（LeetCode）

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

 队列长度法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""# 判断是不是空二叉树if not root:return []# 先把根节点放入队列queue = collections.deque([root])res = []# 然后逐层放入队列再弹出while queue:# 每层储存在level数组里level = []for _ in range(len(queue)):# 弹出根节点，存值cur = queue.popleft()level.append(cur.val)# 队列添加左右节点if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)# 每层走完res.append(level)return res

递归法

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""# 递归法levels = []self.helper(root, 0, levels)return levelsdef helper(self, node, level, levels):# 退出条件if not node:return# 当层数和levels的长度相等的时候，也就是满二叉树的时候，需要再加上一个新的层if len(levels) == level:levels.append([])levels[level].append(node.val)self.helper(node.left, level + 1, levels)self.helper(node.right, level + 1, levels)

107. 二叉树的层序遍历 II - 力扣（LeetCode）

只需要倒序输出即可，代码和上面102保持一致。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def levelOrderBottom(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if not root:return []queue = collections.deque([root])res = []while queue:levels = []for _ in range(len(queue)):cur = queue.popleft()levels.append(cur.val)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)res.append(levels)# 反向输出即可return res[::-1]

199. 二叉树的右视图 - 力扣（LeetCode）

只需要每次把levels最后一个也就是最右侧的节点赋值给res即可。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def rightSideView(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return []res = []queue = collections.deque([root])while queue:levels = []for _ in range(len(queue)):cur = queue.popleft()levels.append(cur.val)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)# 只需要每次把levels最后一个也就是左右侧的节点赋值给res即可res.append(levels[-1])return res

637. 二叉树的层平均值 - 力扣（LeetCode）

只需要在求出每层的基础上求平均即可。

注意作除法之前需要类型转换为float。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def averageOfLevels(self, root):""":type root: TreeNode:rtype: List[float]"""if not root:return []res = []queue = collections.deque([root])while queue:levels = []for _ in range(len(queue)):cur = queue.popleft()levels.append(cur.val)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)# 需要强制类型转换为浮点数sum_ = float(sum(levels))len_ = float(len(levels))avg = sum_ / len_res.append(avg)return res

429. N 叉树的层序遍历 - 力扣（LeetCode）

只需要把children列表里的元素按照顺序取出即可。

"""
# Definition for a Node.
class Node(object):def __init__(self, val=None, children=None):self.val = valself.children = children
"""class Solution(object):def levelOrder(self, root):""":type root: Node:rtype: List[List[int]]"""if not root:return []res = []queue = collections.deque([root])while queue:levels = []for _ in range(len(queue)):cur = queue.popleft()levels.append(cur.val)# children按列表储存childfor child in cur.children:queue.append(child)res.append(levels)return res

 515. 在每个树行中找最大值 - 力扣（LeetCode）

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def largestValues(self, root):""":type root: TreeNode:rtype: List[int]"""if not root:return []res = []queue = collections.deque([root])while queue:level = []for _ in range(len(queue)):cur = queue.popleft()level.append(cur.val)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)# 每层最大值赋值给resres.append(max(level))return res

116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

"""
# Definition for a Node.
class Node(object):def __init__(self, val=0, left=None, right=None, next=None):self.val = valself.left = leftself.right = rightself.next = next
"""class Solution(object):def connect(self, root):""":type root: Node:rtype: Node"""if not root:return root  # 注意这一题的返回值是根节点地址，相当于只在原链表的基础上做修改queue = collections.deque([root])while queue:level = []for _ in range(len(queue)):cur = queue.popleft()# queue的下一个值其实就是next需要指向的地址# if _ < len(queue) - 1:#   cur.next = queue[0]level.append(cur)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)# 在每一层遍历for i in range(len(level) - 1):level[i].next = level[i + 1]return root

 117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

"""
# Definition for a Node.
class Node(object):def __init__(self, val=0, left=None, right=None, next=None):self.val = valself.left = leftself.right = rightself.next = next
"""class Solution(object):def connect(self, root):""":type root: Node:rtype: Node"""if not root:return root  # 注意这一题的返回值是根节点地址，相当于只在原链表的基础上做修改queue = collections.deque([root])while queue:level = []for _ in range(len(queue)):cur = queue.popleft()# queue的下一个值其实就是next需要指向的地址# if _ < len(queue) - 1:#   cur.next = queue[0]level.append(cur)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)# 在每一层遍历for i in range(len(level) - 1):level[i].next = level[i + 1]return root    

104. 二叉树的最大深度 - 力扣（LeetCode）

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def maxDepth(self, root):""":type root: TreeNode:rtype: int"""# 广度优先if not root:return 0cnt = 0queue = collections.deque([root])while queue:# 构造一层的队列for _ in range(len(queue)):cur = queue.popleft()if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)# 构造完加一cnt += 1return cnt# 递归法if not root:return 0else:left_height = self.maxDepth(root.left)right_height = self.maxDepth(root.right)return max(left_height, right_height) + 1# 精简递归return 0 if not root else max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

111. 二叉树的最小深度 - 力扣（LeetCode）

找到第一个叶子节点就退出while。这里用到了flag标记。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""# 广度优先if not root:return 0cnt = 0queue = collections.deque([root])flag = 0while queue:# 构造一层的队列for _ in range(len(queue)):cur = queue.popleft()if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)if not (cur.left or cur.right):flag = 1cnt += 1# 构造完加一if flag:breakreturn cnt

226. 翻转二叉树 - 力扣（LeetCode）

深度遍历

omg！baseline只需要上面的套模板即可实现！！这不神奇吗？？！！

根据顺序做具体的微调

前序/后续

只需要在原来代码的基础上加上子节点的交换过程即可。

递归法里的写法：

root.left, root.right = root.right, root.left

 迭代法里的写法：

node = stack.pop()   
node.left, node.right = node.right, node.left

中序

需要注意中序在执行完交换之后原来的左节点是右节点，但是right指针指向的是原left节点，所以需要在两次递归的时候都要指向left。

self.invertTree(root.left)
root.left, root.right = root.right, root.left
selfinvertTree(root.left)

广度遍历（层序遍历）

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def invertTree(self, root):""":type root: TreeNode:rtype: TreeNode"""# 层序遍历if not root:return rootqueue = collections.deque([root])while queue:for _ in range(len(queue)):node = queue.popleft()# 对于取出队列里的每一个节点交换左右子节点node.left, node.right = node.right, node.leftif node.left:queue.append(node.left)if node.right:queue.append(node.right)return root

101. 对称二叉树 - 力扣（LeetCode）

递归

 思路是分别比较两个子树的内侧和外侧，然后将结果取交集返回中间节点。所以确定便利的顺序一定是后序遍历（最后一个确定中间节点）。

因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""# 递归法if not root:return Truereturn self.compare(root.left, root.right)def compare(self, left, right):"""左----右----result空    空     True空    有     False有    空     False有 != 有     False有 == 有     True"""if left == None and right == None:return Trueelif left == None and right != None:return Falseelif left != None and right == None:return Falseelif left.val != right.val:return Falseelse:  # 此时已经说明left == right，需要再判断他们的子节点outside = self.compare(left.left, right.right)  # 外侧子节点inside = self.compare(left.right, right.left)  # 内侧子节点is_same = outside and inside  # 求交集return is_same

 层序遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""# 层次法queue = collections.deque([root])while queue:level_val = []  # 只需要保存值for _ in range(len(queue)):node = queue.popleft()if node:level_val.append(node.val)queue.append(node.left)queue.append(node.right)else:  # 空节点赋值为Nonelevel_val.append(None)if level_val != level_val[::-1]:  # 倒序比较数组return Falsereturn True

队列或栈

关键：成对取出外侧和内侧节点进行比较。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def isSymmetric(self, root):""":type root: TreeNode:rtype: bool"""# 栈或队列（队列只要把栈改成队列，pop搞成popleft就可以了）if not root:return Truestack = []stack.append(root.left)stack.append(root.right)while stack:left = stack.pop()right = stack.pop()if left == None and right == None:continue  # 注意在while里需要continueif left == None or right == None or left.val != right.val:return Falsestack.append(left.left)stack.append(right.right)stack.append(left.right)stack.append(right.left)return True

2个相关题

100. 相同的树 - 力扣（LeetCode）

两个树，如果采用层序遍历的方法最好把重复部分封装成一个整体的函数。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def isSameTree(self, p, q):""":type p: TreeNode:type q: TreeNode:rtype: bool"""# 层次法queue1 = collections.deque([p])queue2 = collections.deque([q])while queue1 and queue2:if len(queue1) != len(queue2):return Falselevel1 = self.get_level(queue1)level2 = self.get_level(queue2)if level1 != level2:return Falsereturn Truedef get_level(self, queue):level_val = []for _ in range(len(queue)):node = queue.popleft()if node:level_val.append(node.val)queue.append(node.left)queue.append(node.right)else:level_val.append(None)return level_val

 572. 另一棵树的子树 - 力扣（LeetCode）

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def isSubtree(self, root, subRoot):""":type root: TreeNode:type subRoot: TreeNode:rtype: bool"""# 深度遍历+递归if not root:return Falsereturn self.check_is_same(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)def check_is_same(self, root, subroot):if root == None and subroot == None:return Trueelif root == None or subroot == None or root.val != subroot.val:return Falsereturn self.check_is_same(root.left, subroot.left) and self.check_is_same(root.right, subroot.right)

第15天完结🎉