代码编织梦想

关注二叉树的三个问题:

  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。
    • 若当前节点值大于参考值,返回该节点值(可能是第二小值)。
    • 递归遍历左右子树,获取左右子树中可能的第二小值 leftright
  3. 处理子树返回结果
    • left 小于0,返回 right;若 right 小于0,返回 left;若都大于等于0,返回 min(left, right)
  4. 最终调用
    • 外部调用 helper 函数从根节点开始遍历二叉树,返回最终找到的第二小值(若不存在则为 -1)。

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

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_47868976/article/details/144059586

二叉树的遍历及其例题(数据结构学习笔记)-爱代码爱编程

文章目录 先序、中序、后序遍历递归算法1、先序遍历过程先序遍历算法代码2、中序遍历过程中序遍历算法代码3、后序遍历过程后序遍历算法代码层次遍历算法算法设计思路算法代码算法世界复杂度为 O(n)算法例题例题7-11算法思路解题标程例题7-12算法思路解题标程例题7-13算法思路解题标程例题7-14算法思路算法设计例题7-15算法思路解题标程例题7-1

94. 二叉树的中序遍历(Leetcode刷题笔记 )-爱代码爱编程

94. 二叉树的中序遍历(Leetcode刷题笔记 ) 欢迎大家访问我的GitHub博客 https://lunan0320.github.io/ 文章目录 94. 二叉树的中序遍历(Leetcode刷题笔记 )题目解题代码C++(递归)解题代码C++(非递归,栈迭代实现中序遍历)算法效率 题目 给定一个二叉树的根节点 ro

144. 二叉树的前序遍历(二叉树)(Leetcode刷题笔记)-爱代码爱编程

144. 二叉树的前序遍历(二叉树)(Leetcode刷题笔记) 欢迎大家访问我的GitHub博客 https://lunan0320.cn 文章目录 144. 二叉树的前序遍历(二叉树)(Leetcode刷题笔记)题目解题代码 C++ (递归)解题代码 C++(迭代法)算法效率 题目 给你二叉树的根节点 root ,返回它

145. 二叉树的后序遍历(二叉树)(Leetcode刷题笔记)-爱代码爱编程

145. 二叉树的后序遍历(二叉树)(Leetcode刷题笔记) 欢迎大家访问我的GitHub博客 https://lunan0320.cn 文章目录 145. 二叉树的后序遍历(二叉树)(Leetcode刷题笔记)题目解题代码 C++(递归)解题代码 C++(迭代)算法效率 题目 给你一棵二叉树的根节点 root ,返回其

最全二叉树:完整详解二叉树的遍历以及完全二叉树等6种二叉树-爱代码爱编程

2)然后先序遍历左子树 3)然后先序遍历右子树 还是举例说明,先序遍历下图 如果按照先序(根左右)遍历,结果将为: ABDFECGHI 2.3 中序遍历(左根右) 1)先中序遍历左子树 2)然后是根结点 3)然后中序遍历右子树 还是举例说明,中序遍历同一颗二叉树 按照中序遍历(左根右),结果为: DBEFAGHCI 2.4 后序

机器学习周志华学习笔记-爱代码爱编程

机器学习周志华学习笔记-第6章<支持向量机> 6支持向量机 支持向量机是一种经典的二分类模型,是一种监督学习算法。基本模型定义为特征空间中最大间隔的线性分类器,其学习的优化目标便是间隔最大化,因此支持向量机本

阅读《先进引信技术的发展与展望》识别和控制部分_笔记-爱代码爱编程

基本信息 题名:先进引信技术的发展与展望 作者: 张合;戴可人 发表时间:2023-07-20 可装定、可探测、可处理、可控制是灵巧引信设计的四项基本能力。与之对应,先进引信的基础研究涵盖了信息交联技术、末端探测技术、目标识别技术与瞬态控制技术四个主要方面。 1 目标识别技术 目标识别技术主要有近炸目标的分类识别和侵彻目标的结构识别,前

l13.【leetcode笔记】合并两个有序数组-爱代码爱编程

1.题目 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums

learn git branching 学习笔记-爱代码爱编程

一、基础篇 1.1 git commit 1.1.1 示例(git commit) git commit 1.1.2 题目(两次提交记录) git commit git commit 前 后 1.2 git bra

gitlab工作笔记-爱代码爱编程

gitlab常用操作 gitlab常用笔记docker 安装模式pull imagerun一个gitlab container atttach入containerdocker run 之后要等几分钟安装

二叉树的前序遍历 、二叉树的最大深度、平衡二叉树、二叉树遍历【leetcode刷题日志】_平衡二叉树深度遍历-爱代码爱编程

目录 一、二叉树的前序遍历  方法一:全局变量记录节点个数 方法二:传址调用记录节点个数 二、二叉树的最大深度 三、平衡二叉树 四、二叉树遍历 一、二叉树的前序遍历    方法一:全局变量记录节点个数 计算树的节点数: 函数TreeSize用于递归地计算二叉树中的节点数。如果树为空(即根节点为NULL),则返回0。否则,

leetcode刷题笔记第144题:二叉树的前序遍历_leecode刷题 144-爱代码爱编程

LeetCode刷题笔记第144题:二叉树的前序遍历 题目: 给你二叉树的根节点root ,返回它节点值的前序遍历。 想法: 前序遍历是通过根左右的方式遍历整个树,通过递归的方式遍历树 # Definition f

leetcode刷题笔记第145题:二叉树的后序遍历-爱代码爱编程

LeetCode刷题笔记第145题:二叉树的后序遍历 题目: 给定一棵二叉树的根节点 root ,返回其节点值的后序遍历 。 想法: 后序遍历的是通过对树经过“左右根”的顺序进行遍历。使用递归的方式,先遍历左子树,再