张家界做网站,零基础月做网站多久,目前最好的oa系统,wordpress文章群发工具二叉树的广度优先搜索即从上到下、从左到右地进行搜索#xff0c;对于层序遍历#xff08;Level Order#xff09;问题#xff0c;即依次遍历第一层节点、第二层节点…等#xff0c;基本可以秒杀。
广度优先搜索是通过队列来实现的#xff0c;python中优先用collections…二叉树的广度优先搜索即从上到下、从左到右地进行搜索对于层序遍历Level Order问题即依次遍历第一层节点、第二层节点…等基本可以秒杀。
广度优先搜索是通过队列来实现的python中优先用collections.deque因为deque的 popleft() 比列表的 pop(0) 快不少。
剑指 Offer 32 - I. 从上到下打印二叉树
import collections # leetcode里面可以去掉下面都省略
class Solution:def levelOrder(self, root: TreeNode) - List[int]:ans list()if not root:return ansqueue collections.deque()queue.append(root)while queue:node queue.popleft()ans.append(node.val)if node.left: # 左子节点非空加入队列queue.append(node.left)if node.right: # 右子节点非空加入队列queue.append(node.right)return ans从根节点开始每个节点入队之后在出队的时候把它的左右子节点也入队如果非空则该队列就完成了广度优先搜索。
102. 二叉树的层序遍历 (剑指 Offer 32 - II. 从上到下打印二叉树 II)
class Solution:def levelOrder(self, root: TreeNode) - List[List[int]]:ans list()if not root: # 判断空树return ansqueue collections.deque()queue.append(root)while queue:curLevel list()for i in range(len(queue)):node queue.popleft()curLevel.append(node.val)if node.left: # 左子节点非空加入队列queue.append(node.left)if node.right: # 右子节点非空加入队列queue.append(node.right)ans.append(curLevel)return ans需要把同一层的节点放到同一个数组中方法是用一个当前层数组 curLevel通过循环每次把同一层的节点的子节点全部入队同时将这些节点的值记录到curLevel 中一层节点遍历完之后将 curLevel 加入结果数组 ans 中。
103. 二叉树的锯齿形层序遍历剑指 Offer 32 - III. 从上到下打印二叉树 III
class Solution:def levelOrder(self, root: TreeNode) - List[List[int]]:ans list()if not root: # 判断空树return ansqueue collections.deque()queue.append(root)odd True # 奇偶层标志while queue:curLevel list()for i in range(len(queue)):node queue.popleft()curLevel.append(node.val)if node.left: # 左子节点非空加入队列queue.append(node.left)if node.right: # 右子节点非空加入队列queue.append(node.right)if odd:ans.append(curLevel)odd Falseelse:ans.append(curLevel[::-1])odd Truereturn ans按照之字形顺序打印二叉树只需要加个奇偶层标志即可。
1609. 奇偶树
class Solution:def isEvenOddTree(self, root: Optional[TreeNode]) - bool:if not root: # 判断空树return anslevel 0queue collections.deque()queue.append(root)while queue:curLevel []for i in range(len(queue)):node queue.popleft()if (level % 2 0 and node.val % 2 0) or (level % 2 ! 0 and node.val % 2 ! 0):return Falseelse:if len(curLevel) 0:curLevel.append(node.val)elif (level % 2 0 and node.val curLevel[-1]) or (level % 2 ! 0 and node.val curLevel[-1]):return FalsecurLevel.append(node.val)if node.left: # 左子节点非空加入队列queue.append(node.left)if node.right: # 右子节点非空加入队列queue.append(node.right)level 1return True根据所在层数的奇偶判断节点值的奇偶以及递增或递减是否符合奇偶树的要求。
107. 二叉树的层序遍历 II
class Solution:def levelOrderBottom(self, root: TreeNode) - List[List[int]]:ans list()if not root:return ansqueue collections.deque()queue.append(root)while queue:curLevel list()for i in range(len(queue)):node queue.popleft()curLevel.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)ans.append(curLevel)return ans[::-1]唯一区别就是输出结果时倒转输出。
226. 翻转二叉树
class Solution:def invertTree(self, root: TreeNode) - TreeNode:if not root:returnqueue collections.deque()queue.append(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层序遍历时交换节点的左右子节点就完成了翻转二叉树用前中后序遍历的写法见这篇文章。
104. 二叉树的最大深度
class Solution:def maxDepth(self, root: Optional[TreeNode]) - int:if not root:return 0queue collections.deque()queue.append(root)depth 0while queue:depth 1for _ in range(len(queue)):node queue.popleft()if node.left:queue.append(node.left)if node.right:queue.append(node.right)return depth二叉树的最大深度就是二叉树的层数。
111. 二叉树的最小深度
class Solution:def minDepth(self, root: TreeNode) - int:if not root:return 0queue collections.deque()queue.append(root)depth 1while queue:for i in range(len(queue)):node queue.popleft()if not node.left and not node.right:return depthif node.left: # 左子节点非空加入队列queue.append(node.left)if node.right: # 右子节点非空加入队列queue.append(node.right)depth 1只需要用depth记录层数当遇到叶节点就返回depth即为最小深度。
199. 二叉树的右视图
class Solution:def rightSideView(self, root: TreeNode) - List[int]:ans list()if not root:return ansqueue collections.deque()queue.append(root)while queue:n len(queue)for i in range(n):node queue.popleft()if i n - 1:ans.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return ans结果需要的是每一层的最右边的数因此循环到最右边的数时才将节点加入结果数组 ans。
513. 找树左下角的值
class Solution:def findBottomLeftValue(self, root: TreeNode) - int:if not root:return 0queue collections.deque()queue.append(root)while queue:curLevel list()for i in range(len(queue)):node queue.popleft()curLevel.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)return curLevel[0]结果需要的是最底层的最左边节点的值因此用curLevel数组记录每层的节点值最后返回curLevel[0]就是最底层的最左边节点的值。
1302. 层数最深叶子节点的和
class Solution:def deepestLeavesSum(self, root: Optional[TreeNode]) - int:# 题目说了非空树queue collections.deque()queue.append(root)while queue:curLevel 0for i in range(len(queue)):node queue.popleft()curLevel node.valif node.left:queue.append(node.left)if node.right:queue.append(node.right)return curLevel返回最后一层的节点之和。
637. 二叉树的层平均值
class Solution:def averageOfLevels(self, root: TreeNode) - List[float]:ans list()if not root:return ansqueue collections.deque()queue.append(root)while queue:currLevel list()n len(queue)for i in range(n):node queue.popleft()currLevel.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)ans.append(mean(currLevel))return ans结果需要的是每一层的平均数因此将平均数加入结果数组 ans。
515. 在每个树行中找最大值
class Solution:def largestValues(self, root: TreeNode) - List[int]:ans list()if not root:return ansqueue collections.deque()queue.append(root)while queue:currLevel list()n len(queue)for i in range(n):node queue.popleft()currLevel.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)ans.append(max(currLevel))return ans结果需要的是每一层的最大数因此将最大数加入结果数组 ans。
1161. 最大层内元素和
class Solution:def maxLevelSum(self, root: TreeNode) - int:if not root:return 0queue collections.deque()queue.append(root)MaxValue -float(inf)ans 1depth 1while queue:curLevel 0for i in range(len(queue)):node queue.popleft()curLevel node.valif node.left:queue.append(node.left)if node.right:queue.append(node.right)if curLevel MaxValue:MaxValue curLevelans depthdepth 1return ans目标是找到层值之和最大的那一层记录层数和最大值即可注意 MaxValue 初始值要设成负无穷 -float(‘inf’) 。
429. N 叉树的层序遍历 # Definition for a Node.
class Node:def __init__(self, valNone, childrenNone):self.val valself.children childrenimport collections
class Solution:def levelOrder(self, root: Node) - List[List[int]]:ans list()if not root:return ansqueue collections.deque()queue.append(root)while queue:curLevel list()for i in range(len(queue)):node queue.popleft()curLevel.append(node.val)for child in node.children: # 区别if child:queue.append(child)ans.append(curLevel)return ansN叉数是 children 列表而二叉树是 left 和 right 遍历 children 即可。
116. 填充每个节点的下一个右侧节点指针
class Solution:def connect(self, root: Node) - Node:if not root:return rootqueue collections.deque()queue.append(root)while queue:size len(queue)for i in range(size):node queue.popleft()if i size - 1: # 必须使用 sizenode.next queue[0]if node.left:queue.append(node.left)if node.right:queue.append(node.right)return root层序遍历一次二叉树记录节点是队列先进先出的所以左边的节点先出来它的 next 就为 queue[0]注意 len(queue) 是会变化的所以必须使用 size 记录一层的长度。
117 . 填充每个节点的下一个右侧节点指针 II
class Solution:def connect(self, root: Node) - Node:if not root:return rootqueue collections.deque()queue.append(root)while queue:size len(queue)for i in range(size):node queue.popleft()if i size - 1:node.next queue[0]if node.left:queue.append(node.left)if node.right:queue.append(node.right)return root不完美的二叉树但是和上一题一模一样的代码。
623. 在二叉树中增加一行
class Solution:def addOneRow(self, root: TreeNode, val: int, depth: int) - TreeNode:if depth 1:new_root TreeNode(val val, left root, right None)return new_rootqueue collections.deque()queue.append((root, 1))while queue:for _ in range(len(queue)):node, d queue.popleft()if d depth - 1:old_left node.leftold_right node.rightnode.left TreeNode(val val, left old_left, right None)node.right TreeNode(val val, left None, right old_right)else:if node.left:queue.append((node.left, d1))if node.right:queue.append((node.right, d1))return root如果在第一行增加那就是创建一个新的根节点然后将原根节点作为左子节点。否则的话就在队列中使用多一个参数 d 来记录深度在 d - 1 层进行增加一行的操作先记住节点原来的左右子节点 old_left 与 old_right然后创建新的节点即可。关键是必须使用 for 循环对整个第 d - 1 层都进行同样的操作。
662. 二叉树最大宽度
class Solution:def widthOfBinaryTree(self, root: Optional[TreeNode]) - int:ans 1if not root:return 0queue collections.deque()queue.append((root, 1))while queue:cur []for _ in range(len(queue)):node, pos queue.popleft()cur.append(pos)if node.left:queue.append((node.left, 2 * pos - 1))if node.right:queue.append((node.right, 2 * pos))if max(cur) - min(cur) 1 ans:ans max(cur) - min(cur) 1return ans在队列中使用多一个参数 pos 来记录位置只需要记住的是位置为 pos 的节点从 1 开始的左子节点位置是 2 * pos - 1右子节点的位置是 2 * pos。
958. 二叉树的完全性检验
class Solution:def isCompleteTree(self, root: TreeNode) - bool:queue collections.deque()queue.append((root, 1))depth 0while queue:if len(queue) 2**depth:for i in range(len(queue)):node, pos queue.popleft()if node.left:queue.append((node.left, pos*2-1))if node.right:queue.append((node.right, pos*2))depth 1else:for i in range(len(queue)):node, pos queue.popleft()if node.left or node.right or (i1) ! pos:return Falsereturn True与上一题类似的关键是记录节点的位置注意位置从 1 开始。在满层中正常遍历一旦遇到不满的层如果其中有非叶子节点或者位置对不上则不是完全二叉树。
993. 二叉树的堂兄弟节点
class Solution:def isCousins(self, root: TreeNode, x: int, y: int) - bool:# x 和 y 的深度与父节点x_depth, x_parent, y_depth, y_parent None, None, None, None level 0queue collections.deque([(root, None)])while queue:n len(queue)level 1for i in range(n):node, node_parent queue.popleft()# 每个节点的值都是唯一的if node.val x:x_depth levelx_parent node_parentif node.val y:y_depth levely_parent node_parentif node.left:queue.append((node.left, node))if node.right:queue.append((node.right, node))return x_depth y_depth and x_parent ! y_parent由于题目中说明每个节点的值都是唯一的所以用四个变量分别表示 x 和 y 的深度与父节点。然后在队列中要同时记录节点和节点的父节点如果遇到值为 x 或 y 的节点就记录其深度和父节点最后进行比较即可。
