当前位置： 首页 > article >正文

【二叉树】【2.1遍历二叉树】【刷题笔记】【灵神题单】

article 2024/11/27 16:03:49

关注二叉树的三个问题：

  1. 什么情况适合自顶向下？什么时候适合用自底向上？
  2. 一般来说，DFS的递归边界是空节点，什么情况下要额外把叶子节点作为递归边界？
  3. 在什么情况下，DFS需要有返回值？什么情况不需要有返回值？

三种遍历顺序

本质就是根节点位置决定前中后序遍历！

  1. 前序遍历
    • 顺序：根节点 - 左子树 - 右子树。
    • 特点：先处理根节点，然后依次深入左子树和右子树进行相同规则的遍历。可以快速获取根节点相关信息，适用于复制二叉树等操作。
  2. 中序遍历
    • 顺序：左子树 - 根节点 - 右子树。
    • 特点：对于二叉搜索树，能得到有序的节点序列。先深入左子树，再访问当前层根节点，最后遍历右子树，常用于二叉搜索树的排序相关操作。
  3. 后序遍历
    • 顺序：左子树 - 右子树 - 根节点。
    • 特点：最后处理根节点，在删除二叉树节点或者需要先获取左右子树信息（如计算二叉树高度）的场景比较适用，先递归处理左右子树，最后处理根节点。

144.二叉树的前序遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         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: return

            res.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, val=0, left=None, right=None):
#         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: return
           
            dfs(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, val=0, left=None, right=None):
#         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 res

872.叶子相似的树

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         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 = []
            # 当前空节点，直接return
            if not node:
                return
            
            # 递归到了叶子节点
            if node.left is node.right:
                ans.append(node.val)
            # 前序遍历？
            dfs(node.left)
            dfs(node.right)
            return ans
        return 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):
            
            # 当前空节点，直接return
            if 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 ans
        ans1 = dfs(root1, ans1)
        ans2 = dfs(root2, ans2)

        return ans1 == ans2

LCP44.开幕式焰火

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:
                return
            s.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:
                return
            s.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, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.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:
            return
        q = []
        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, val=0, left=None, right=None):
		self.val = val
		self.right = right
		self.left = left

class Solution:
	def sumOfLeftLeaves(self, root):
		res = []
		if root is None:
			return result
		
		q = []
		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, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        res = 0
        def dfs(node, is_left):
            nonlocal res

            if node is None:
                return
            # 关键逻辑，is_left递归决定是否dfs
            if node.left is None and node.right is None and is_left:
                res += node.val
            dfs(node.left, True)
            dfs(node.right, False)
        dfs(root, False)
        return res
一开始没加nonlocal一直通过不了！！
如果dfs函数内部没有用nonlocal声明res，python会认为在dfs内部重新定义了一个局部变量res，（尽管我实际上是想操作外层函数中的那个res），并且因为我在用res之前没有对这个新认为的局部变量进行初始化，所以会抛出unboundlocalerrro的错误，提示无法访问一个没有关联值的局部变量
当我加了nonlocal res后，就明确告诉了python解释器，在dfs函数中操作的res是来自外层函数的那个以及已经初始化过的局部变量，这样就能正确找到。

671.二叉树中第二小的节点

  • 这道题很难么？我认为只要检查根节点的左右子节点就行，如果根节点的左右子节点都相等，才需要递归检查左右子树，
  • 直到发现第一次不相等，不等于根节点那个值就是第二大的值，我这个思路对不对？

不对！！！

  1. 类比欧冠比赛来理解二叉树问题
    • 冠军（根节点最小值）的确定方式：
      • 在欧冠比赛中，冠军是通过层层比赛筛选出来的最强队伍。在二叉树中，根节点的值被定义为左右子节点中的最小值（root.val = min(root.left.val, root.right.val)），这就好像冠军是从左右两个“分区”（左右子树）中选出的最小值一样。
    • 第二强队伍（第二小值）的复杂性：
      • 在欧冠比赛中，亚军不一定是第二强的队伍。因为比赛的赛制是淘汰赛，可能有其他很强的队伍在和冠军队伍比赛前就被淘汰了，这些队伍也许比亚军更强。类比到二叉树中，只看根节点的左右子节点来确定第二小的值是不准确的。就像比赛中有很多队伍在淘汰赛过程中被淘汰一样，二叉树中的节点值也存在多种情况。
      • 例如，在二叉树中，即使根节点的左右子节点相等，在子树的更深处可能存在比根节点大，但比当前左右子节点小的值，这就好像在比赛中，有一些队伍虽然没有直接和冠军竞争，但实力介于冠军和我们最初认为的“亚军”（根节点左右子节点）之间。
    • 第二强队伍（第二小值）与冠军（根节点最小值）的关联：
      • 你说的“第二强的一定和冠军交过手”类比到二叉树中，有一定的相似性。在二叉树中，真正的第二小的值一定是和根节点的值（最小的值）有比较关系的。它要么是根节点左右子节点中的较大值（如果存在差异），要么是在子树中比根节点值大的其他值。但不能简单地通过根节点左右子节点来判断，而是要遍历整个二叉树，就像要考虑整个欧冠比赛的所有队伍一样，来找到所有比根节点值大的节点值，然后从中确定第二小的值。
  2. 总结
    • 这个类比很形象地说明了不能简单地根据二叉树的局部结构（如根节点左右子节点）来确定第二小的值，而是要像考虑整个欧冠比赛的队伍情况一样，全面地考虑二叉树中所有节点的值，才能准确地找到第二小的值。

所以本质上这道题还是遍历

遍历 + 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 findSecondMinimumValue(self, root: TreeNode) -> int:
        """先序遍历+set"""
        s = set()
        def dfs(node):
            if not node:
                return           
            nonlocal s
            s.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为val
                min2 = min1    # 更新min2
                min1 = val     # 
            elif val < min2 :  # val比min1大比min2小，就是第二大| 或者等于，也就是第二大的值！！！
                min2 = val     # min2已经更新为上一轮的min1了！，此时val就是第二大的min2！
        return -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 = None

class 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 right
            if right < 0:
                return left
            # 如果左右都有返回值，小的才是我们要找的第二小！
            return min(left, right)

        return helper(root, root.val)
  1. 定义辅助函数
    • 定义 helper 函数，接受当前节点 root 和参考值 val（初始为根节点值）。
  2. 递归遍历与判断
    • 若当前节点为空，返回 -1。
    • 若当前节点值大于参考值，返回该节点值（可能是第二小值）。
    • 递归遍历左右子树，获取左右子树中可能的第二小值 left 和 right。
  3. 处理子树返回结果
    • 若 left 小于0，返回 right；若 right 小于0，返回 left；若都大于等于0，返回 min(left, right)。
  4. 最终调用
    • 外部调用 helper 函数从根节点开始遍历二叉树，返回最终找到的第二小值（若不存在则为 -1）。

总的来说，这段代码通过深度优先搜索（DFS）的方式递归地遍历二叉树，在遍历过程中根据节点值与参考值的比较以及左右子树的返回结果来逐步确定可能的第二小的值，直到遍历完整个二叉树得出最终答案。


http://www.kler.cn/a/411557.html

相关文章：

  • 【vue3实现微信小程序】从轮播图到公告栏的前端开发之旅
  • JDBC 批量调用数据库 SQL, 函数与存储过程
  • PICO 获取设备号 SN码
  • 【JavaScript】JavaScript开篇基础（7）
  • DHCP服务（包含配置过程）
  • 鸿蒙开发Hvigor插件动态生成代码
  • 【小白学机器学习36】关于独立概率，联合概率，交叉概率，交叉概率和，总概率等 概念辨析的例子
  • 堆排序实现
  • Linux服务器驱动安装
  • HarmonyOS：应用沙箱
  • 源码解读笔记：协程的 ViewModel.viewModelScope和LifecycleOwner.lifecycleScope
  • 【MCU】微控制器的编程技术：ISP 与 IAP
  • VTS：基于Apache SeaTunnel的开源向量数据迁移工具
  • 鸿蒙学习自由流转与分布式运行环境-跨端迁移(2)
  • C++ STL - vector/list讲解及迭代器失效
  • 数据结构——小小二叉树第三幕（链式结构的小拓展，二叉树的创建，深入理解二叉树的遍历）超详细！！！
  • Vue进阶面试题目（四）
  • 【设计模式】【创建型模式（Creational Patterns）】之原型模式（Prototype Pattern）
  • 25A物联网微型断路器 智慧空开1P 2P 3P 4P-安科瑞黄安南
  • C# 泛型 学习理解记录
  • vue3+ts 我写了一个跟swagger.yml生成请求和响应实体（接口）
  • 电商平台数据获取：解锁商业洞察的多元渠道
  • #Verilog HDL# Verilog中的UDP原语
  • 2024算法基础公选课练习五（DFS2）
  • 前端---CSS（部分用法）
  • C++的中的继承