【2025-03-01】基础算法：二叉树递归数学归纳法栈

用户11029137

发布于 2025-03-02 22:28:28

8100

代码可运行

文章被收录于专栏：编程学习

运行总次数：0

代码可运行

一，递归简述

递归经典模板：

1，前序遍历

def dfs(node, param):
    if not node:
        return
    # 处理当前节点（从上往下）
    new_param = update(param, node.val)
    dfs(node.left, new_param)
    dfs(node.right, new_param)

参数传递，从上到下传播

2，后序遍历

def dfs(node):
    if not node:
        return 0
    left = dfs(node.left)
    right = dfs(node.right)
    # 合并子节点结果（从下往上）
    return merge(left, right, node.val)

返回值汇总，从下往上

3，中序遍历

def inorder_traversal(root):
    result = []
    
    def traverse(node):
        if not node:
            return
        traverse(node.left)    # 遍历左子树
        result.append(node.val)  # 访问根节点
        traverse(node.right)   # 遍历右子树
    
    traverse(root)
    return result

4，结合两种方式的示例(先序和后序)

def hasPathSum(root, targetSum):
    def dfs(node, current_sum):
        if not node:
            return False
        current_sum += node.val  # 从上往下传递路径和
        if not node.left and not node.right:
            return current_sum == targetSum  # 叶子节点返回结果（从下往上）
        return dfs(node.left, current_sum) or dfs(node.right, current_sum)  # 合并子节点结果
    return dfs(root, 0)

二，视频题目

104. 二叉树的最大深度

把正在写的本层想做是上层，调用自身函数的时候接收到的是下层的结果返回。而下层的结果又是来自于下下层，直到最底层满足边界条件的时候，开始“回归”

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
    #     if root is None:
    #         return 0
    #     l_depth = self.maxDepth(root.left)
    #     r_depth = self.maxDepth(root.right)
    #     return max(l_depth, r_depth) + 1

    # 从上往下
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node, depth):
            if node is None:
                return
            depth += 1 
            nonlocal ans  # 全局变量（用来进行状态的传递和更新）
            ans = max(ans, depth)
            dfs(node.left, depth)
            dfs(node.right, depth)
        dfs(root, 0) # 切记这里传入0，进去函数以后depth+1代表root的深度
        return ans

三，课后作业

111. 二叉树的最小深度

从上到下：

# 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 minDepth(self, root: Optional[TreeNode]) -> int:
        ans = inf
        def dfs(node, depth):
            nonlocal ans # 声明是全局变量
            if node is None:
                return
            depth += 1
            if node.left is None and node.right is None:
                ans = min(ans, depth)
                return # 提前返回，因为已经是叶子节点了，没有左右子树可以再输入dfs了
            dfs(node.left, depth)
            dfs(node.right, depth)
        dfs(root, 0)
        return ans if root else 0

从下到上

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        elif root.right is None:
            return self.minDepth(root.left) + 1
        elif root.left is None:
            return self.minDepth(root.right) + 1
        else:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1

112. 路径总和

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        # 每一层返回的True或者False也会被传递
        if root is None:
            return False
        targetSum -= root.val
        if root.left is None and root.right is None:
            return targetSum == 0
        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

129. 求根节点到叶节点数字之和

# 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 sumNumbers(self, root: Optional[TreeNode], x = 0) -> int:
        # dfs从上往下的思想，但是回归的时候还是最底层先返回
        if root is None:
            return 0
        x = x * 10 + root.val
        if root.left is None and root.right is None:
            return x
        return self.sumNumbers(root.left, x) + self.sumNumbers(root.right, x)

1448. 统计二叉树中好节点的数目

# 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 goodNodes(self, root: Optional[TreeNode], mx=-inf) -> int:
        if root is None:
            return 0
        left = self.goodNodes(root.left, max(root.val, mx)) # 参数传递，上到下
        right = self.goodNodes(root.right, max(root.val, mx)) # 在本层里mx不考虑root.val
        return left + right + (mx <= root.val) # 结果汇总，从下到上

987. 二叉树的垂序遍历

题解：

# 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 verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        hasmap = defaultdict(list) # 和字典类似，但是默认元素为list
        def dfs(node, row, col):
            nonlocal hasmap
            if node is None:
                return 
            hasmap[col].append((row, node.val)) # 按col分组，添加每个节点的(row, ndoe.val)
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)
        dfs(root, 0, 0)

        ans = []
        for _, g in sorted(hasmap.items()): # items()得到的是键值对
            # sorted(hasmap.items()) : 按照col进行排序
            # g得到的是每一个col对应的列表，元素是(row, val)
            g.sort() # 先按第一个元素 row 排序，row 相同按 val 排序
            ans.append([val for _, val in g])
        return ans

四，sort()和sorted()重要用法

核心区别

特性	list.sort()	sorted()
返回值	原地排序，返回 None	返回新列表，原列表不变
适用对象	仅列表	任何可迭代对象（列表、元组、字典等）
时间复杂度	O(n log n)	O(n log n)
稳定性	稳定排序（相同键值保持原始顺序）	稳定排序

基础用法

1. 默认排序（升序）

# list.sort()
nums = [3, 1, 4, 1, 5]
nums.sort()           # 原地排序，nums 变为 [1, 1, 3, 4, 5]

# sorted()
nums = [3, 1, 4, 1, 5]
sorted_nums = sorted(nums)  # 返回新列表 [1, 1, 3, 4, 5]

2. 逆序排序（降序

nums.sort(reverse=True)          # 原地降序 [5, 4, 3, 1, 1]
sorted_nums = sorted(nums, reverse=True)  # 新列表降序

核心技巧

1. 自定义排序规则（`key` 参数）

按元素的某个属性或计算结果排序。
key 是一个函数，接受元素，返回排序依据的值。

# 按字符串长度排序
words = ["apple", "banana", "cherry", "date"]
words.sort(key=lambda x: len(x))  # ['date', 'apple', 'banana', 'cherry']

# 按元组的第二个元素排序
pairs = [(1, 3), (2, 1), (3, 2)]
sorted_pairs = sorted(pairs, key=lambda x: x[1])  # [(2, 1), (3, 2), (1, 3)]

2. 多条件排序

如果第一个条件相同，按第二个条件排序，依此类推。

# 先按长度排序，长度相同按字母逆序
words = ["apple", "banana", "date", "cherry"]
sorted_words = sorted(words, key=lambda x: (len(x), -ord(x[0])))
# 结果：['date', 'apple', 'cherry', 'banana']

3. 逆序的灵活使用

# 按第二个元素降序排序
pairs = [(1, 3), (2, 1), (3, 2)]
sorted_pairs = sorted(pairs, key=lambda x: -x[1])  # [(1, 3), (3, 2), (2, 1)]

4. 处理复杂数据结构

# 对字典列表按某个键排序
students = [
    {"name": "Alice", "score": 90},
    {"name": "Bob", "score": 85},
    {"name": "Charlie", "score": 95}
]
sorted_students = sorted(students, key=lambda x: x["score"])  # 按分数升序

5. 稳定排序的利用

多次排序实现多级排序（先排次要条件，再排主要条件）。

# 先按姓排序，再按名排序（假设原列表已按名排序）
names = [("Alice", "Smith"), ("Bob", "Brown"), ("Charlie", "Smith")]
names.sort(key=lambda x: x[1])  # 先按姓排序
names.sort(key=lambda x: x[0])  # 再按名排序（稳定排序保留姓的顺序）

高效技巧（算法优化）

1. 避免重复计算

预处理数据以减少 key 函数的计算量。

# 预处理：将字符串长度存储为元组
words = ["apple", "banana", "cherry", "date"]
words_with_len = [(len(w), w) for w in words]
words_with_len.sort()  # 按长度排序

2. 利用切片快速逆序

sorted_nums = sorted(nums)[::-1]  # 等效于 reverse=True

3. 处理大数据的排序

当数据量极大时，优先使用 sorted 生成新列表，避免原地修改可能的内存问题。

常见应用场景

1. 区间合并问题

# 按区间起点排序，再合并重叠区间
intervals = [[1,3], [2,6], [8,10], [15,18]]
intervals.sort(key=lambda x: x[0])

2. 任务调度（贪心算法）

# 按结束时间排序，选择最早结束的任务
tasks = [(1, 4), (3, 5), (0, 6)]
tasks.sort(key=lambda x: x[1])

3. 自定义对象的排序

class Node:
    def __init__(self, val, priority):
        self.val = val
        self.priority = priority

nodes = [Node(3, 2), Node(1, 1), Node(2, 2)]
nodes.sort(key=lambda x: (x.priority, x.val))  # 先按优先级，再按值