网页设计网站的分析,如何在京东上开网店,网站注册协议,wordpress ajax -1本文图片来源#xff1a;代码随想录 层序遍历#xff08;图论中的广度优先遍历#xff09; 这一部分有10道题#xff0c;全部可以套用相同的层序遍历方法#xff0c;但是需要在每一层进行处理或者修改。 102. 二叉树的层序遍历 - 力扣#xff08;LeetCode#xff09;
层… 本文图片来源代码随想录 层序遍历图论中的广度优先遍历 这一部分有10道题全部可以套用相同的层序遍历方法但是需要在每一层进行处理或者修改。 102. 二叉树的层序遍历 - 力扣LeetCode
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助数据结构即队列来实现队列先进先出符合一层一层遍历的逻辑而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。 队列长度法
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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, valNone, childrenNone):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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone, nextNone):self.val valself.left leftself.right rightself.next next
class Solution(object):def connect(self, root)::type root: Node:rtype: Nodeif 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, val0, leftNone, rightNone, nextNone):self.val valself.left leftself.right rightself.next next
class Solution(object):def connect(self, root)::type root: Node:rtype: Nodeif 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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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
深度遍历
omgbaseline只需要上面的套模板即可实现这不神奇吗 根据顺序做具体的微调 前序/后续
只需要在原来代码的基础上加上子节点的交换过程即可。
递归法里的写法
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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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有 有 Trueif 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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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, val0, leftNone, rightNone):
# 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天完结
