傻瓜动态建站 工具,互联网app推广,济源做网站怎么收费,商检局做产地证的网站关注二叉树的三个问题#xff1a;
什么情况适合自顶向下#xff1f;什么时候适合用自底向上#xff1f;一般来说#xff0c;DFS的递归边界是空节点#xff0c;什么情况下要额外把叶子节点作为递归边界#xff1f;在什么情况下#xff0c;DFS需要有返回值#xff1f;什…关注二叉树的三个问题
什么情况适合自顶向下什么时候适合用自底向上一般来说DFS的递归边界是空节点什么情况下要额外把叶子节点作为递归边界在什么情况下DFS需要有返回值什么情况不需要有返回值
三种遍历顺序
本质就是根节点位置决定前中后序遍历
前序遍历 顺序根节点 - 左子树 - 右子树。特点先处理根节点然后依次深入左子树和右子树进行相同规则的遍历。可以快速获取根节点相关信息适用于复制二叉树等操作。 中序遍历 顺序左子树 - 根节点 - 右子树。特点对于二叉搜索树能得到有序的节点序列。先深入左子树再访问当前层根节点最后遍历右子树常用于二叉搜索树的排序相关操作。 后序遍历 顺序左子树 - 右子树 - 根节点。特点最后处理根节点在删除二叉树节点或者需要先获取左右子树信息如计算二叉树高度的场景比较适用先递归处理左右子树最后处理根节点。
144.二叉树的前序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) - List[int]:res []def dfs(node):if node is None: returnres.append(node.val) # 根节点值 dfs(node.left) # 左节点dfs(node.right) # 右节点dfs(root)return res
94.二叉树的中序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) - List[int]:res []def dfs(node):if node is None: returndfs(node.left)res.append(node.val)dfs(node.right)dfs(root)return res
145.二叉树的后序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def postorderTraversal(self, root: Optional[TreeNode]) - List[int]:res []def dfs(node):if not node: return dfs(node.left)dfs(node.right)res.append(node.val)dfs(root)return res872.叶子相似的树
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) - bool:# dfs 递归到叶子节点时当前节点无左右子节点将当前节点值放入res[]# 用啥顺序遍历def dfs(node):ans []# 当前空节点直接returnif not node:return# 递归到了叶子节点if node.left is node.right:ans.append(node.val)# 前序遍历dfs(node.left)dfs(node.right)return ansreturn dfs(root1) dfs(root2)
——————————————————————
解答错误
21 / 47 个通过的测试用例官方题解
输入
root1
[1,2,3]
root2
[1,3,2]添加到测试用例
输出
true
预期结果
false以为是递归顺序的原因换成了中序遍历结果并没有改变。
这段代码的核心错误在于每次每次调用dfs函数都重新初始化了一个空列表[ ]这样就无法正确地在整棵树地遍历过程中收集到所有叶子节点的值到一个统一的列表
正确做法是在函数外部初始化结果列表ans1和ans2然后将这个列表不断递归更新每次都传入下一层递归函数
class Solution:def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) - bool:# dfs 递归到叶子节点时当前节点无左右子节点将当前节点值放入res[]# 用啥顺序遍历ans1 []ans2 []def dfs(node, ans):# 当前空节点直接returnif not node:return # 递归到了叶子节点if node.left is None and node.right is None:ans.append(node.val) # 前序遍历dfs(node.left, ans)dfs(node.right, ans)return ansans1 dfs(root1, ans1)ans2 dfs(root2, ans2)return ans1 ans2LCP44.开幕式焰火
DFS 前序遍历 set()
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right None
class Solution:def numColor(self, root: TreeNode) - int:# DFS 前序遍历 set()s set()def dfs(node, s):if node is None:returns.add(node.val)dfs(node.left, s)dfs(node.right, s)dfs(root, s)return len(s)或者把s非重复字典放到dfs函数外面也可以实现这个逻辑。为什么
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right None
class Solution:def numColor(self, root: TreeNode) - int:# DFS 前序遍历 set()s set()def dfs(node):if node is None:returns.add(node.val)dfs(node.left)dfs(node.right)dfs(root)return len(s)两种方式区别在于 set 的定义位置与传递形式不同效果一样是因为都利用 set 去重特性遍历二叉树时添加节点值并最终返回其元素个数来统计不同节点值数量。
BFS 层遍历 队列
层次遍历顺序按照树的层次一层一层地向下遍历直到队列为空。 这里地遍历顺序是广度优先地按层遍历从根节点开始每层从左到右一次访问节点。
# Definition for a binary tree node.
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right right
class Solution:def numColor(self, root):s set()self.search(s, root)return len(s)def search(self, s, node):if node is None:returnq []q.append(node)while q:current_node q.pop(0)s.add(current_node.val)if current_node.left:q.append(current_node.left)if current_node.right:q.append(current_node.right)404.左叶子之和
返回所有左叶子值之和为了理解如何找到左叶子先不完成这道题的要求先写一个dfs来判断如何找到左叶子。
DFS写法
def (node, is_left):if node is None:return# 判断是否为左叶子节点if node.left is None and node.right is None and is_left:res.append(node.val)dfs(node.left, True)dfs(node.right, False)dfs(root, False)BFS写法
class TreeNode:def __inti__(self, val0, leftNone, rightNone):self.val valself.right rightself.left leftclass Solution:def sumOfLeftLeaves(self, root):res []if root is None:return resultq []q.append((root, False))while q:current_node, is_left q.pop(0)# 判断是否是左叶子节点if current_node.left is None and current_node.right is None and s_left:result.append(current_node.val)if current_node.left:q.append((current_node.left, True))if current_node.right:q.append((current_node.right, False))return result 以上是如何遍历左叶子的方法 下面完成本题任务加和所有左叶子值
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def sumOfLeftLeaves(self, root: Optional[TreeNode]) - int:res 0def dfs(node, is_left):nonlocal resif node is None:return# 关键逻辑is_left递归决定是否dfsif node.left is None and node.right is None and is_left:res node.valdfs(node.left, True)dfs(node.right, False)dfs(root, False)return res
一开始没加nonlocal一直通过不了
如果dfs函数内部没有用nonlocal声明respython会认为在dfs内部重新定义了一个局部变量res尽管我实际上是想操作外层函数中的那个res并且因为我在用res之前没有对这个新认为的局部变量进行初始化所以会抛出unboundlocalerrro的错误提示无法访问一个没有关联值的局部变量
当我加了nonlocal res后就明确告诉了python解释器在dfs函数中操作的res是来自外层函数的那个以及已经初始化过的局部变量这样就能正确找到。
671.二叉树中第二小的节点
这道题很难么我认为只要检查根节点的左右子节点就行如果根节点的左右子节点都相等才需要递归检查左右子树直到发现第一次不相等不等于根节点那个值就是第二大的值我这个思路对不对
不对
类比欧冠比赛来理解二叉树问题 冠军根节点最小值的确定方式 在欧冠比赛中冠军是通过层层比赛筛选出来的最强队伍。在二叉树中根节点的值被定义为左右子节点中的最小值root.val min(root.left.val, root.right.val)这就好像冠军是从左右两个“分区”左右子树中选出的最小值一样。 第二强队伍第二小值的复杂性 在欧冠比赛中亚军不一定是第二强的队伍。因为比赛的赛制是淘汰赛可能有其他很强的队伍在和冠军队伍比赛前就被淘汰了这些队伍也许比亚军更强。类比到二叉树中只看根节点的左右子节点来确定第二小的值是不准确的。就像比赛中有很多队伍在淘汰赛过程中被淘汰一样二叉树中的节点值也存在多种情况。例如在二叉树中即使根节点的左右子节点相等在子树的更深处可能存在比根节点大但比当前左右子节点小的值这就好像在比赛中有一些队伍虽然没有直接和冠军竞争但实力介于冠军和我们最初认为的“亚军”根节点左右子节点之间。 第二强队伍第二小值与冠军根节点最小值的关联 你说的“第二强的一定和冠军交过手”类比到二叉树中有一定的相似性。在二叉树中真正的第二小的值一定是和根节点的值最小的值有比较关系的。它要么是根节点左右子节点中的较大值如果存在差异要么是在子树中比根节点值大的其他值。但不能简单地通过根节点左右子节点来判断而是要遍历整个二叉树就像要考虑整个欧冠比赛的所有队伍一样来找到所有比根节点值大的节点值然后从中确定第二小的值。 总结 这个类比很形象地说明了不能简单地根据二叉树的局部结构如根节点左右子节点来确定第二小的值而是要像考虑整个欧冠比赛的队伍情况一样全面地考虑二叉树中所有节点的值才能准确地找到第二小的值。
所以本质上这道题还是遍历
遍历 set() 排序
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def findSecondMinimumValue(self, root: TreeNode) - int:先序遍历sets set()def dfs(node):if not node:return nonlocal ss.add(node.val)dfs(node.left)dfs(node.right)dfs(root)min1 float(inf) # 最小min2 float(inf) # 第二小# 则关键逻辑是找到s中有没有一个val满足 min1 val min2 # 如果for val in s:if val min1: # 存在一个val比最小的min1还要小就说明要更新min1为val且更新min2为valmin2 min1 # 更新min2min1 val # elif val min2 : # val比min1大比min2小就是第二大| 或者等于也就是第二大的值min2 val # min2已经更新为上一轮的min1了此时val就是第二大的min2return -1 if min2 float(inf) else min2 另一种写法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val x
# self.left None
# self.right Noneclass Solution:def findSecondMinimumValue(self, root: TreeNode) - int:先序遍历def helper(root, val): # 当前要遍历的节点用于比较的值val调用的时候直接调用根节点值也就是最小值 if not root: # 递归终止条件到头return -1 # 这道题找值这里应该返回值有的题不返回值# 关键逻辑val是要比较的值root.val是当前节点的值if root.val val:# 当前节点值大于参考值当前值有可能是第二小return root.val# 递归遍历左右子树且传入当前节点值作为参考# 如果走到头都没有发现比val大的返回-1表示这条路不存在left helper(root.left, val) # 注意这里val并没有在每次递归时改变right helper(root.right, val) # val始终时根节点也就是最小# 处理左右子树返回的结果如果某个子树返回的值是-1即到头没发现第二小就返回另一边树的值if left 0:return rightif right 0:return left# 如果左右都有返回值小的才是我们要找的第二小return min(left, right)return helper(root, root.val) 定义辅助函数 定义 helper 函数接受当前节点 root 和参考值 val初始为根节点值。 递归遍历与判断 若当前节点为空返回 -1。若当前节点值大于参考值返回该节点值可能是第二小值。递归遍历左右子树获取左右子树中可能的第二小值 left 和 right。 处理子树返回结果 若 left 小于0返回 right若 right 小于0返回 left若都大于等于0返回 min(left, right)。 最终调用 外部调用 helper 函数从根节点开始遍历二叉树返回最终找到的第二小值若不存在则为 -1。
总的来说这段代码通过深度优先搜索DFS的方式递归地遍历二叉树在遍历过程中根据节点值与参考值的比较以及左右子树的返回结果来逐步确定可能的第二小的值直到遍历完整个二叉树得出最终答案。
